art-hack's blog

Modified Knapsack Problem
By art-hack, history, 5 years ago, In English

I created a problem, but I couldn't solve it and need some help.

Problem You have N blocks with an array a in which a[i] represents the weight of ith item. You are also given the maximum weight that the knapsack can handle as W.

You have to find the maximum possible weight that you can achieve by filling these blocks in the knapsack.

Now the different part is that you can either take any block as whole or you can split it into two blocks(only once) such that atleast one of the two block has weight between [80,100%) and you can take either of the blocks into the knapsack.

Sample Input
2
200 100
285

Sample Output
285

Sample Input
2
200 100
230
Sample Output
220

Explaination: In the first sample input we take the first block as whole and the second partially with one piece of 85 and one of 15 and take the one with weight 85 to achieve the total of 285.

In the second sample input we take the first block as whole and the second partially with one piece of 80 and one of 20 and take the one with weight 20 to achieve the total of 220.

I wanted to know if it is solvable or not.

If possible can we extend this question with another given array v representing the values of the blocks and we want to achieve the maximum possible value by putting blocks in the knapsack. Note: when we split a block its value gets split in the same ratio as it's weight.

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

»
5 years ago, # |
← Rev. 13   Vote: I like it 0 Vote: I do not like it

found O(NW)

just count 2 dp: the first is normal dp[0], the second using separation dp[1]

then dp[1][i][j] = dp[1][i-1][j] or dp[1][i-1][j-arr[i]] or (dp[0][i-1][j-x]) or (dp[0][i-1][j-y]):

x = (0-20%) * a[i] : X = (j- a[i]*0.2, j )

y = (80-100%) * a[i] : Y = (j — a[i], j — a[i]*0.8)

to find out if on segment X or Y true, you can use prefix sum

(sorry, translate.google)

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

    How do we handle the fact that the percentages cab be non integers as well?

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

      ok, dp[1][i][j] — double

      dp[1][i][j] == -1 if unattainable value,else dp[1][i][j] == x =[0,1] — fractional part. if segment(l+1, r)==true -> x=1 else if dp[0][i-1][l] -> x = fractional part a[i]*y%.

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

    Yeah, this solution works great as I checked with various inputs.

    Any ideas on extending the solution to achieve maximum value when we extend the question with an array v, denoting the value of each block?

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

      1)use a tricky segment_tree instead of a prefix, but I'm too lazy to think

      2)**O(N*W^2)**(for little W)

      We calculate dp from two sides (prefix and suffix) then the answer is without i block = prefix[i-1] # suffix[i+1] //O(W^2)

      try for each achievable value add 20-% or 80+%

      maybe # == * and it can be reduced to FFT(O(wlogw)), but I'm not so strong

      → Reply