Unbounded Knapsack in Python
Given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, the task is to determine the maximum value that can be obtained by putting items into the knapsack. In the Unbounded Knapsack problem, you can use each item as many times as you want.
Example:
Input: Weights:
[1, 3, 4, 5]
, Values:[10, 40, 50, 70]
, Capacity:8
Output:
The maximum value obtainable is: 140
Input: Weights:
[2, 3, 5]
, Values:[15, 20, 30]
, Capacity:7
Output
: The maximum value obtainable is: 140
To solve the Unbounded Knapsack problem, we use a dynamic programming approach. We define a
dp
array wheredp[i]
represents the maximum value that can be achieved with a knapsack capacityi
.
Implementation of Unbounded Knapsack in Python
- Initialize a
dp
array of sizeW+1
with all elements set to 0. This array will store the maximum value that can be achieved for each capacity from0
toW
. - Iterate over each possible knapsack capacity from
0
toW
. For each capacityi
, we check all items to see if they can fit into the knapsack. - If an item can fit into the knapsack (i.e., its weight is less than or equal to the current capacity
i
), we update thedp
array at positioni
to be the maximum of its current value or the value obtained by including the item. This is calculated asdp[i - weights[j]] + values[j]
. - The value at
dp[W]
will be the maximum value that can be achieved with the given weight capacityW
.
Below is the Python code to implement the Unbounded Knapsack problem:
def unbounded_knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(capacity + 1):
for j in range(n):
if weights[j] <= i:
dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
return dp[capacity]
# Example usage
weights = [1, 3, 4, 5]
values = [10, 40, 50, 70]
capacity = 8
max_value = unbounded_knapsack(weights, values, capacity)
print(f"The maximum value obtainable is: {max_value}")
Output
Maximum value: 110
Complexity Analysis
- Time Complexity:O(n×W), where
n
is the number of items andW
is the maximum capacity of the knapsack. This is because we iterate through each capacity and for each capacity, we iterate through all items. - Auxiliary Space Complexity: O(W) due to the
dp
array used to store the maximum value for each capacity.