maghrabyJr_'s blog

By maghrabyJr_, history, 2 years ago, In English

hello codeforces!

Today I thought of this variation of the knapsack problem and I couldn't find a solution.

We have $$$n$$$ items ($$$n$$$ is up to $$$10^{6}$$$). There are $$$sz_i$$$ copies of the $$$i_{th}$$$ item.

$$$\sum sz_i$$$ won't exceed $$$10^6$$$

We can pick more than one copy of each item, if we decided to pick $$$j$$$ copies of the $$$i_{th}$$$ item our score increases by $$$value[i][j]$$$

Our goal is to pick $$$k$$$ ($$$k$$$ is up to $$$10^6$$$) copies in total in a way that will maximize our score.

This sounds very standard to me, what is the solution for that?

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

| Write comment?
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

isn't this an Unbounded Knapsack problem?

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If $$$value[i]$$$ is concave in $$$j$$$ for all $$$i$$$, then simply picking the biggest $$$k$$$ differences is correct.

If not, then for $$$2$$$ kinds of objects each of size $$$2k$$$, this is $$$(+, max)$$$ convolution, which (I think) is hard to do subquadratically.