Knapsack variation.

Правка en2, от maghrabyJr_, 2022-04-01 04:46:43

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?

Теги dp, knapsack

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский maghrabyJr_ 2022-04-01 04:46:43 0 (published)
en1 Английский maghrabyJr_ 2022-04-01 04:45:54 567 Initial revision (saved to drafts)