Modified Knapsack Problem

Revision en1, by art-hack, 2019-08-27 11:10:40

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 weight of the knapsack as W.

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

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.

Tags #dynamic programing, #range query, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English art-hack 2019-08-27 11:48:30 41
en2 English art-hack 2019-08-27 11:15:07 32 Tiny change: 'n200 100\n285\nSam' -> 'n200 100\n\n285\nSam'
en1 English art-hack 2019-08-27 11:10:40 1387 Initial revision (published)