Knapsack, Weight-Only - Dynamic Programming / Knapsack

Problems
24

thanks!

25

top down Java solution with comments

public static List knapsackWeightOnly(List weights) {
Set result = new HashSet<>();

   allSums(weights, 0, result, 0, new HashMap<>());
    
   return new ArrayList<>(result);
}

private static void allSums(List<Integer> weights, int index, Set<Integer> result, int sum, Map<Integer, Set<Integer>> memo)
{
    // if the result has been computed before do nothing 
    if(memo.containsKey(index) && memo.get(index).contains(sum))
        return;
    
    // add the sum to the list
    if (index == weights.size())
        result.add(sum);
    
    else 
    {
        // just pass on the sum and icrease the index
        allSums(weights, index + 1, result, sum, memo); 
        
        // add the curent weight to the sum and icrease the index
        allSums(weights, index + 1, result, sum + weights.get(index), memo);
        
        // Add the sum of the index to the memo to avoid calling it again
        Set<Integer> sumSet = memo.getOrDefault(index, new HashSet<>());
        sumSet.add(sum); 
        memo.put(index, sumSet);
       
    }
}
26

Thanks for posting this! I also noticed that the Js solution was missing the line where we set the memo to true and wasn’t able to find out why…

27

In top-down method explanation, why is " And Node B’s subtree has leaf values of 3, 8, 6, 11."?

28

typo
In the “Top-down Dynamic Programming” and “Memoization, identifying the state” section, the sentence
“Node A’s subtree has leaf values of 3 and 8. And Node B’s subtree has leaf values of 3, 8, 6, 11.” should be “Node B’s subtree has leaf values of 3 and 8. And Node A’s subtree has leaf values of 3, 8, 6, 11.”

29

thanks!

30

Python bottom up solution

def knapsack_weight_only(weights: List[int]) → List[int]:
max_sum = sum(weights)
n = len(weights)
dp = [[False for _ in range(max_sum + 1)] for _ in range(n+1)]

dp[0][0] = True # we can make sum 0 with first 0 elements of weights 

for i in range(1, n+1):
    for j in range(max_sum+1): 
        # can we make sum j with the first i elements of weights?
        current_weight = weights[i-1] # the newly considered element 
        dp[i][j] = dp[i-1][j] or (j - current_weight >= 0 and dp[i-1][j - current_weight]) 
        # true if j in previous row is true because we can just not put the newly considered element.
        # or true if we can get to current j by adding our current_weight. We check this by checking if the previous
        # row's j - current_weight column is True
    
        

return [i for i in range(len(dp[-1])) if dp[-1][i] == True]
31

Node B’s subtree has leaf values of 3 and 8. And Node A’s subtree has leaf values of 3, 8, 6, 11.

32

I had the same question. Why is the tree binary in this case as opposed to like Combination Sum, where each edge is valid (non-visited or duplicate) value from the list?

33

In Combination Sum, input numbers can be used unlimited number of times so at each level we try every element. In this problem each element can only be used once, so we use/not use in each level.

1 Like
34

In the javascript bottom-up approach on line 4, you have for weight in weights It should be for weight of weights This error causes the last 2 test cases to timeout as it’s iterating over the properties names rather than the array elements.

Also, on line 18, dp[i][w] || dp[i - 1][w]; the left hand side of the OR operation is redundant as dp[i][w] is always false at that point, so the result will always bee the right hand side of the OR.

35

True, but I think we can just use dedup logic like in other problems to achieve the same end. For example, the code below seems to work.

function knapsackWeightOnly(weights) {
    function dfs(start, sum, res) {
        res.add(sum);
        for (let i = start; i < weights.length; i++) {
            if (i === start || weights[i] !== weights[i - 1]) {
                const weight = weights[i];
                dfs(i + 1, sum + weight, res);
            }
        }
    }
    weights.sort();
    const ans = new Set();
    dfs(0, 0, ans, memo);
    return [...ans];
}

My questions are:

  1. does this more aggressive approach to pruning not achieve the same time complexity as if we memoized? and
  2. if not, is there still a way to memoize when modeling the tree this way?
37

In the bottom up solution I think that:

dp[i][w] = dp[i][w] or dp[i - 1][w]

can be simplified to:

dp[i][w] = dp[i - 1][w]

since dp[i][w] hasn’t yet been updated at this stage in the loop and will always be False.