For this problem, I just ran the most basic knapsack with the weights as weights and talent for values, then for each weight >= W in the knapsack compared the ratios of dp[weight] * 1000 / weight and took the largest ratio. My code passed all 10 test cases but the intended solution with binary search + dp seems much more complicated.
Link: http://www.usaco.org/index.php?page=viewproblem2&cpid=839
Code: https://pastebin.com/EBvTcx0f
Share code? How do you do knapsack on weights when the sum of the weights is huge?
Oh, I misread the bounds; I thought each weight only went up to 1000.
Looks like the weights in the test data are pretty small for the most part …
The sum of the weights does exceed what I put for MXW in test cases 4-10 but apparently none of the answers require the sum of weights being higher than MXW.
Orz hi benq, here’s my understanding of the question.
If you knapsack and use talent as one of the dp states (instead of weight), then you still get AC, but scdivad doesn’t know if this is the intended solution.
My solution would not have worked if the test data was stricter, so it was not the intended solution.
Yeah, this solution was not supposed to work. Counter cases can be easily generated, but the test data was weak.
I did the same thing and here is why i think it works. If a weight is more then required, and it’s ratio is the best one out of all other weight greater, it is best to just take that weight. Otherwise, we can use the dp to figure out the best answer with weights less then the required.
Well, it doesn’t work. But we can actually solve this problem in \mathcal{O}(nW) time.
oh ok I see. I guess this is why my solution passed.