You are not logged in. Please login at www.codechef.com to post your questions!

×

Hints Needed Huge Knapsack

2
1

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.

asked 06 Jan, 13:55

nickzuck_007's gravatar image

nickzuck_007
190417
accept rate: 14%

Guys, please help

(10 Jan, 20:39) nickzuck_007

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 :D
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 :)

link

answered 11 Jan, 06:51

meooow's gravatar image

meooow
4494
accept rate: 37%

edited 11 Jan, 06:53

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, 00:30) nickzuck_007

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, 22:36) meooow

Can we make it a problem of 3-D dp ???

(12 Jan, 23:04) nickzuck_007

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, 01:10) meooow
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×1,034
×559
×13

Asked: 06 Jan, 13:55

Seen: 531 times

Last updated: 14 Jan, 01:10