# Hints Needed Huge Knapsack

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

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