I need to map an optimization problem to a bounded knapsack problem.
I have a set of items, each with a given value vi. All my items have the same weight (wi = 1) :
- Item 1 => v1 : 2, w1 : 1
- Item 2 => v2 : 3, w2 : 1
- Item 3 => v3 :4, w3 :1
- etc.
In my knapsack I can put the same item multiple times (bounded Knapsack) with the constraint that the number of items added to the knapsack cannot exceed c (and, hence, each item cannot be added more than c times).
The problem is that the value assigned to an item is dependent on the previous content of the bag : each time an item is added to knapsack, its value is divided by the number of occurrence of the item in the bag. For example, if item 1 is added two times to the knapsack, its value must be decreased to v1/2. If it is added 3 times, its value became v1/3, and so on.
My question is how can I modelize this as a (0-1) knapsack problem and is there a DP solution for that?