NguyenKhacTrung's blog

Can knapsack with w,v <=10^9 ?
By NguyenKhacTrung, history, 13 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

Comments Comments (16)
| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any other condition specified? Probably there's.

→ Reply
»
13 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 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
»
13 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://codeforces.net/blog/entry/97396

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    How is that true? Pick elements: $$$1, 2, 4, 8, 16, 32, \ldots, 2^n$$$. Each number from $$$[0, 2^{n+1})$$$ can be obtained as a sum of some subset. We have sum $$$w = 2^{n+1} - 1$$$ and $$$w + 1$$$ possible sums of subsets.

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You did not understand that blog. N in that blog is the sum (or maybe more precisely the sum being O(N)). That'd give us O(totalweight^1.5) in here, which is obviously useless.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      Yeah you are right, my sincere apologies, I didn't read the blog carefully, what a shame.

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

Can you add a link to the problem?

→ Reply