# 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()
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!
Grad you’re enjoying the platform 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()

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

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

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

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

const result = [];

for (let w = 0; w <= totalSum; w++) {
if (dp[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 = true;
dp = true;
for (int i = 1; i <= size; i++) {
for (int w = 0; w <= totalSum; w++) {
if (w - weights[i - 1] >= 0) {
dp[w] = dp[w] || dp[w - weights[i - 1]];
}
}

``````    dp = dp;
}

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

}