Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem

ACMer

4 years ago

You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and value of the ith item.

Given that you can take at most capacity weights, and that you can take any number of copies for each item, return the maximum amount of value you can get.

Constraints
n ≤ 250 where n is the length of weights and values
capacity ≤ 250
Example 1
Input
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
Output
11

Unbounded Knapsack Problem solved by Dynamic Programming Algorithm

This is a typical unbounded knapsack problem where you can pack as many as items per item-type as long as there is enough capacity. The DP (Dynamic Programming) equation is:

where c is the capacity and i is the index between 0 to N-1 where N is the number of items. w is the weights and v is the values array.

class Solution:
    def uboundedKnapsack(self, weights, values, capacity):
        dp = [0] * (capacity + 1)
        for i in range(1, capacity + 1):
            for j in range(len(weights)):
                if i >= weights[j]:
                    dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
        return max(dp)

class Solution:
    def uboundedKnapsack(self, weights, values, capacity):
        dp = [0] * (capacity + 1)
        for i in range(1, capacity + 1):
            for j in range(len(weights)):
                if i >= weights[j]:
                    dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
        return max(dp)

The above Python implementation of Dynamic Programming to solve the Unbounded Knapsack problem has time complexity O(CW) and space complexity O(C).

C++ implementation of the same DP algorithm:

int uboundedKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    for (int i = 1; i <= capacity; ++ i) {
        for (int j = 0; j < weights.size(); ++ j) {
            if (i >= weights[j]) {
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j]);
            }
        }
    }
    return *max_element(begin(dp), end(dp));
}

int uboundedKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    for (int i = 1; i <= capacity; ++ i) {
        for (int j = 0; j < weights.size(); ++ j) {
            if (i >= weights[j]) {
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j]);
            }
        }
    }
    return *max_element(begin(dp), end(dp));
}

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

463 words
Last Post: Teaching Kids Programming - Find the Single Number in Array
Next Post: Teaching Kids Programming - Algorithms to Determine a Happy Number

The Permanent URL is: Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem (AMP Version)

Unbounded Knapsack Problem solved by Dynamic Programming Algorithm

Knapsack Problems

Related posts: