# Knapsack, Weight-Only - Dynamic Programming / Knapsack

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

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

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

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

Updated, thanks!

Updated, thanks!

Still see an old one.

Hi Vladislav, I meant itâ€™ll be included in the next deployment

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

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.

Why isnt there an option to see the solution in the â€śTry-it-yourselfâ€ť portion?

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):

return list(dp)
``````

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

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.

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;
}
``````

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.

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.

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) {
Set<Integer>set = new HashSet<>();
Set<Coordinate>visited = new HashSet<>();
dfs(answer, weights, set, visited, 0, 0);
}

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)) {
}
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);
}
``````

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;
``````

}