ioi_want's blog

Bounded knapsack
By ioi_want, history, 2 months ago, In English

Does any body have judge for this problem? There are N type of items, for type i three integers is given w_i(weight of the item), v_i(value of the item), c_i(the number item that we have). The capacity of knapsack is W. we want to choose some item so that we have the maximum value. What is that value?

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

Comments Comments (4)
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

OK. Does anybody know the solution of the problem?

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

    yes, there is a problem on this mentioned in algorithms live lecture on knapsack on open kattis and stefdasca in his channel has shown the approach to do this in n*w*log(min(n,w)) , i guess! But i have heard this can be done even in O(N*W) using offsets and min-queue but i have never done and am also looking for N*W solution actually.

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

    Pashka is also going to talk about variants of knapsack in his next lecture, so u can get an idea there maybe..

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

    See this video

    → Reply