Can anyone please give me the hints to solve this problem HUGE KNAPSACK. I was thinking about 3-D dp but I think there must be an easy solution than that.
1 Like
Guys, please help
Thought a lot about this one. Finally got AC after many trials, but I think there’s an issue with this problem. For now, let’s roll with it.
Assume that you already know the maximum weight of gold that can be contained in any given volume v as best[v] (classical unbounded knapsack). Now what we need to do is run dp on the sacks. Let dp[i] be the best answer for i sacks, then dp[s] is our required answer. For each i in 1\le i\le s, we split it into j and i-j sacks for 1\le j\le i/2 and consider dp[j]+dp[i-j] as a possible way of filling up i sacks. Also we consider stitching all i sacks together, which would give the value as best[y\times i]-c\times (i-1) (total volume of i sacks is y*i and i-1 stitches are required). This will calculate the answer in \mathcal{O}(s^2), which won’t be a problem.
The problem lies in the first part, calculating the best values. As it turns out, using the greedy approximation to the unbounded knapsack problem gets you AC. But I cannot find any reason why it should. In fact I have found cases where my solution fails spectacularly, but the judge is unable to detect it 
Perhaps the quality of the problem is just poor. Or the testcases are just weak and there is a great solution possibly taking advantage of the tight constraints on w[i] and v[i]. If you do find such a solution I’ll be interested to know! But to get AC the greedy approach will suffice.
Hope this helps 
2 Likes
Thanks for your answer @meooow. While I was waiting for someone to answer on this, I found that people have solved it the Greedy way but was also wondering on the reason for it. Happy to find someone caring about the quality of the problems more than just getting AC.
Yeah… although it would be an interesting problem if it was fixed. Running dp on a dp array would be like “Yo Dawg, I herd you like dp, so I put a dp on your dp so you can dp after you dp” XD
Can we make it a problem of 3-D dp ???
Well I can’t find any way to represent the problem as a dp state of 3 variables… Have you found such a definition?