NguyenKhacTrung's blog

Can knapsack with w,v <=10^9 ?
By NguyenKhacTrung, history, 12 months ago, In English

i have the problem knapsack has condition N<=100 and w,v<=10^9.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any other condition specified? Probably there's.

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

This one has a extra condition $$$w\times v\le 10^9$$$, and I don’t think the problem is solvable without this condition.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please add the link? Or the full statement?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem probably has some other stuff if it is meant to be solvable with this range of values. The best you can do with a small $$$N$$$ would be "meet in the middle", which will still be a TLE if your $$$N \leq 100$$$

→ Reply
»
12 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Vip pro ngừi Việt. As far as i know there's a solution with $$$O(n\sqrt{totalweight})$$$ complexity. So with $$$totalweight=n*w= 1e11$$$ then yeah this solution passes. The idea is that there are about $$$\sqrt{w}$$$ possible sums of subsets when the sum of all of the elements in the set equal $$$w$$$ so we just need to calculate all those possible sums first, then apply the general dp algorithm -> $$$O(n\sqrt{sum})$$$ instead of $$$O(n*sum)$$$. How? I havent implemented it myself but this blog exlains it well and also provides an implementation :D https://mirror.codeforces.com/blog/entry/97396

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you add a link to the problem?

→ Reply