Whistle's blog

A problem that I don't have any idea how to solve it

By Whistle, history, 8 years ago, In English

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

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

Comments Comments (11)
| Write comment?
»
8 years ago, # |
  Vote: I like it -20 Vote: I do not like it

What's wrong with the simple Bounded-Knapsack algorithm?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it -9 Vote: I do not like 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).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ignore. Though that one's budget is S not D.

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

        @Whistle did I misunderstand your problem?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

          → Reply
»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

what he said ^^^

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"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, ... ?

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply