there are N items and a budget of D dollars
each item has a stock S (you can buy at most S of that item) A, B , and value X
the cost for k of that item is (A + (k-1)* B)
what is the maximum value can be attained given this budget ??
1 <= N <=2000
1<= D <= 5000
1<= X,S <= 10^7
0<= B <= A <= D
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
What's wrong with the simple Bounded-Knapsack algorithm?
I couldn't find any clear Bounded-Knapsack tutorial
but in Wikipedia Bounded-Knapsack is as same as this problem but the cost of the second piece of
any item equal the cost of the first piece
can you pleas give any good tutorial for it ?
dp[i][j] ->You can buy only items 1,...,i and you have j dollars,what's the maximum number of items you can buy?
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Ai] + 1, dp[i - 1][j - Ai - Bi] + 2, ..., dp[i - 1][j - Ai - x * Bi] + x + 1)
Except dp[i][j] for all the others ( dp[i][x] ) x%Bi = (j - Ai)%Bi so you can get something like deque to do this things: push_back,pop_front, and return maximum.
Think how to do this without using some extra structure(like set or map).
Ignore. Though that one's budget is S not D.
@Whistle did I misunderstand your problem?
to be honest I don't understand your solution
I think DP should be like this
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Ai] + Xi, dp[i - 1][j - Ai - Bi] + 2 * Xi, ..., dp[i - 1][j - Ai - x * Bi] + x *Xi)
but the second part isn't clear for me
any way , thanks alot for helping me :)
what he said ^^^
"the cost for k of that item is (A + (k-1)* B)" — that is not clear for me
Are costs of following items of that type A, B, B, B, ... or A, A+B, A+2B, ... ?
First one
A,B,B,B...
The exact same problem is available on HackerRank : https://www.hackerrank.com/contests/indeed-prime-codesprint/challenges/hats and it also contains a good editorial