Can anyone please give me the hints to solve this problem HUGE KNAPSACK. I was thinking about 3D dp but I think there must be an easy solution than that. asked 06 Jan '17, 13:55

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 $ij$ sacks for $1\le j\le i/2$ and consider $dp[j]+dp[ij]$ 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 (i1)$ (total volume of i sacks is y*i and i1 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 :D answered 11 Jan '17, 06:51
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.
(12 Jan '17, 00:30)
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
(12 Jan '17, 22:36)
Can we make it a problem of 3D dp ???
(12 Jan '17, 23:04)
Well I can't find any way to represent the problem as a dp state of 3 variables... Have you found such a definition?
(14 Jan '17, 01:10)

Guys, please help