Hello so this is my first blog, I solved knapsack 1 but cant find any solution to solve V2 : https://atcoder.jp/contests/dp/tasks/dp_e

can any one help me ?

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 197 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

5 | awoo | 185 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 175 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

Hello so this is my first blog, I solved knapsack 1 but cant find any solution to solve V2 : https://atcoder.jp/contests/dp/tasks/dp_e

can any one help me ?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2021 19:54:06 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

first you have to find value per weight,then you sort them in descending order. then take one by one

this didn't work for me. It gave correct answer for a few cases, but then it failed 3/4th of the cases.

Could you explain why?

This is a variant of the classic knapsack.

Notice that value is small (at most $$$10^5$$$ for all $$$100$$$ items), so instead of "what is the most value we can carry with weight $$$W$$$", you find "what is the least weight you need to carry to get a value of $$$V$$$".

Can it be done using top-down approach?

I don't see why not :)

The parameters are (the item we are considering, the value we have taken so far) for $$$100*10^5$$$ states. The choices for each state are still "take the item" and "ignore the item", just like in usual knapsack.

Maybe memory limit might be an issue, but I've never had problems with $$$10^7$$$ integer states.

Can't seem to figure it out! If I include the element, I add its weight. And when I don't include the element, I don't add its weight. I have to take the minimum of both the choices. What will be the base case? When I reach the end of the array, I simply return 0.

But it doesn't seem to work! I also seem to understand while writing that it won't work. Where is it wrong and how do I make it work?

Recurrence looks ok to me :) But there are some issues in

`solve2`

I think.`int`

only holds up to $$$2^{31} - 1$$$, so it should overflow.Also in this if else

Shouldn't it be more like this?

Fixed the solve2 method and overflow. Still doesn't give the correct answer. There's some issue in the recursion. Take case:

while calling recursion, at first, it goes on to include all elements, that is the first call, and then hits the base case from where it returns zero. Then the second call i.e. the not include case is called for the last element, from where it gets 0 from the base case. Now dp[n-1][maxV-valueOfLastElement]=0 because of the not include case. Isn't this wrong because it says to get value of [maxV-valueOfLastElement], we need only 0 weight. It didn't add up the weights of previously selected elements.

Yeah looks like we missed that part :)

I guess we're both messing up the definitions a bit here. Usually we define

`dp(i, V)`

as "first i items, we are allowed to take V more values". So the answer should be`dp(N, initialV)`

, and the recurrence actually goes backwards from $$$N$$$ to $$$0$$$ (and likewise, from $$$maxV$$$ to $$$0$$$).So you can implement the same recurrence but backwards (i.e. "if I include the element, I decrease $$$maxV$$$"), and do

Thanks a lot for your hint!!

You may consider iterating over sum of values rather than weights as per the constraints..So making the definition of dp[i] as minimum weight that can be taken with exactly i value..you can iterate on items and value(since constraints on value is low) My submission..https://atcoder.jp/contests/dp/submissions/10848260 ..Also you can refer to Youtube video by Errichto for the same

MidoriFuse dark__forest thanks guys, that helped me

An alternative is Branch and Bound algorithm. Don't simply look at its theoretical time complexity. It works wonders in practice.

You can try Branch and Bound to run faster

SpoilerIt should be noted that the Branch and Bound algorithm doesn't always run fast. It's runtime depends on the accuracy and speed of the cost-estimation function. The better the cost-estimation function, the faster your answer will attain the optimum value. In this case, the cost-estimation function is both good and fast, so Branch and Bound works.

p.s. I don't think you understand how Branch and Bound works. It seems to me that your code uses DP instead of Branch and Bound.

Yes. Thank you for reminding me. Since I always adding Branch and Bound for faster in some specific problems, I forgot to notice that not at every time it work faster than normal approach

Yeah it is Top Down DP !!

https://qr.ae/pNrdrx

This helped me.

How to solve Knapsack-2 in single-d array? Anyone? This is my code and i am really stuck.

Please put codes in spoilers. Your code is incorrect because You do not know if $$$dp[j-values[i-1]]$$$ has already used your current object and you may use it again. To fix that, you may iterate $$$j$$$ in reverse, so you know for a fact $$$dp[j-value[i-1]]$$$ is untouched.

Thanks a lot. It worked.

Refer to this solution in which I have explained Knapsnack 0-1 with all possible implementation 1. Recursive Memoisation 2. Tabulation: space O(n^2) 3. Tabulation: space O(n) 4. The special case when max capacity is large, done using tabulation.

Thanks

Can someone tell me what is wrong with this. I am unable to see the initialisation

In my dp[i][j] ,I stored the minimum weight required to calculate j value using i items

Spoiler... n,w = map(int , input().split())`````` values = [] weights = [] ans= 0 totalvalues = 0 for i in range(n): a,b = map(int ,input().split()) weights.append(a) values.append(b) totalvalues += b

dp = [ [0 for i in range(totalvalues+1)] for j in range(n+1) ] for i in range(totalvalues+1): dp[0][i] = float("inf") for i in range(n+1): dp[i][0] = 0

for i in range(1,n+1): for j in range(1,totalvalues+1): if values[i-1] <= j : dp[i][j] = min(dp[i-1][j], dp[i-1][j-values[i-1]] + weights[i-1]) else : dp[i][j] = dp[i-1][j]

for i in range(1,n+1): for j in range(1,totalvalues + 1): if dp[i][j] <= w: ans = j

print(ans)