Блог пользователя Whistle

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

Автор Whistle, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        @Whistle did I misunderstand your problem?

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
»
9 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

what he said ^^^

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

→ Ответить