Knapsack, Weight-Only - Dynamic Programming / Knapsack

Problems
1

https://algo.monster/problems/knapsack_weight_only

3

Why can’t you solve this problem like this, won’t this get the same runtime O(n*total_sum) but the code is more clean:

def knapsack_weight_only(weights: List[int]) → List[int]:
res = set([0])
for num in weights:
cur_sums = []
for sum_ in res:
if num+sum_ not in res:
cur_sums.append(num+sum_)
res.update(cur_sums)
return list(res)

1 Like
4

The solution is so unoptimal, why would you use vectors with total_sum lengths each? Imagine if you have 100 numbers with values about 10M in that case the length of vectors should be about 1B and you need a loop 1B times! The right approach is to use set of sums combinable with 0-i weights and the number of elements of that set would be doubled on each step in worst case so we have time complexity O(2^n) in worst case. Though it even worse for silly vector with total_sum length

6

In the main function, instead of printing System.out.print(i), it needs to be printing System.out.print(res.get(i))

I changed it and solution is correct now. May just want to change that to show by default.

Love this platform, keep it up :slight_smile:

7

C# output mismatch on equal results and last line in main should join res instead of row

8

Updated, thanks!

9

Updated, thanks!
Grad you’re enjoying the platform :smiley:

11

Still see an old one.

12

Hi Vladislav, I meant it’ll be included in the next deployment

13

@mod memo is not getting updated in memoized version of generate_sums function.

14

Anyone having issues with the tester? the output is not actually whats returned from the code. I tried copying the solution and running the tester, and it failed too.

15

Why isnt there an option to see the solution in the “Try-it-yourself” portion?

16

Isn’t this a strictly better solution?

def knapsack_weight_only(weights: List[int]) → List[int]:
dp = set([0])

for weight in weights:
    for currentWeight in list(dp):
        dp.add(currentWeight + weight)

return list(dp)
17

Problems with multiple solutions currently do not have one-click solution loading function.

18

created github issue https://github.com/realAlgoMonster/contrib/issues/66 to cleanup topdown solution - just in case anyone’s top down solution is not working.

19

JS Bottom-Up solution with space optimization

function knapsackWeightOnly(weights) {
  const n = weights.length;
  const totalSum = weights.reduce((sum, weight) => sum + weight, 0);
  const dp = Array.from(
      { length: 2 },
      () => Array(totalSum + 1).fill(false)
  );
  dp[0][0] = true;

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= totalSum; w++) {
      dp[1][w] = dp[1][w] || dp[0][w];

      if (w >= weights[i - 1]) {
        dp[1][w] = dp[1][w] || dp[0][w - weights[i - 1]];
      }
    }

    for (let w = 0; w <= totalSum; w++) {
      dp[0][w] = dp[1][w];
    }
  }

  const result = [];

  for (let w = 0; w <= totalSum; w++) {
    if (dp[0][w]) result.push(w);
  }

  return result;
}
20

For the python bottom up solution:
Line 11: what is the current item’s weight (w[i-1]), and what is the target weight (w), as in why are they called current item and target? I don’t understand what the check does.

Thank you so much.

21

For the python bottom up solution:
Line 11: what is the current item’s weight (w[i-1]), and what is the target weight (w), as in why are they called current item and target? I don’t understand what the check does.

Thank you so much.

22

To me, using Set with custom class to record visited node is much easier to understand.
Here is a Java example:
private static class Coordinate{
int x;
int y;

    public Coordinate(int xValue, int yValue) {
        this.x = xValue;
        this.y = yValue;
    }
    
    @Override
    public int hashCode() {
        return x + y;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        Coordinate coordinate = (Coordinate)obj;
        return (coordinate.x == x && coordinate.y == y);
    }
}

public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
    List<Integer>answer = new ArrayList<>();
    Set<Integer>set = new HashSet<>();
    Set<Coordinate>visited = new HashSet<>();
    answer.add(0);
    set.add(0);
    dfs(answer, weights, set, visited, 0, 0);
    return answer;
}

private static void dfs(List<Integer>answer, List<Integer> weights, Set<Integer>set, Set<Coordinate>visited, 
                        int index, int sum) {
    Coordinate coordinate = new Coordinate(index, sum);
    if (visited.contains(coordinate)) return;
    if (index == weights.size()) {
        if (!set.contains(sum)) {
            set.add(sum);
            answer.add(sum);
        }
        return;
    }
    
    int next = sum + weights.get(index);
    dfs(answer, weights, set, visited, index + 1, next);
    next = sum;
    dfs(answer, weights, set, visited, index + 1, next);
    visited.add(coordinate);   
}
23

I simplified the last version of the solution in a way that made it easier for me to understand the approach. Hope you find it useful.

std::vector knapsack_weight_only(std::vector weights) {
int totalSum = accumulate(weights.begin(), weights.end(), 0);
int size = weights.size();
vector<vector> dp(2, vector(totalSum + 1, false));
dp[0][0] = true;
dp[1][0] = true;
for (int i = 1; i <= size; i++) {
for (int w = 0; w <= totalSum; w++) {
if (w - weights[i - 1] >= 0) {
dp[1][w] = dp[1][w] || dp[0][w - weights[i - 1]];
}
}

    dp[0] = dp[1];
}

vector<int> ans;
for (int w = 0; w <= totalSum; w++) {
    if (dp[1][w]) {
        ans.push_back(w);
    }
}
return ans;

}