aloalgo0/1 Knapsack Problem: Maximize Value with Binary Choices
You are given a set of items, each with a weight and a value. You are also given a knapsack that has a maximum weight capacity.
Your task is to determine the maximum total value of items that can be placed into the knapsack without exceeding its capacity. You can either take an item or leave it behind; you cannot take a fractional part of an item. Each item can be taken at most once.
Example 1
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
220
By picking the items with weights 20 and 30, we get a total value of 100 + 120 = 220, and the total weight is 20 + 30 = 50, which is within the capacity.
Example 2
weights = [1, 2, 3]
values = [6, 10, 12]
capacity = 5
22
By picking the items with weights 2 and 3, we get a total value of 10 + 12 = 22, and the total weight is 2 + 3 = 5, which is exactly the capacity.
Example 3
weights = [10, 20]
values = [5, 8]
capacity = 5
0
Neither item can fit into the knapsack, so the maximum value is 0.
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
220