Menu
The standard 0/1 knapsack requires that the weight of every item is independent to others. Then DP is a efficient algorithm towards the solution. But now I met a similar but extensions of this problem, that
the weight of new items are dependent on previous items already in the knapsack.
For example, we have 5 items a, b, c, d and e with weight w_a, ..., w_e. item b and c have weight dependency.
When b is already in the knapsack, the weight of item c will be smaller than w_c because it can share some space with b, i.e. weight(b&c) < w_b + w_c. Symmetrically, when c is already in the knapsack, the weight of b will be smaller than w_b.
This uncertainty results a failure of original DP algorithm, since it depend on the correctness of previous iterations which may not correct now. I have read some papers about knapsack but they either have dependencies subjected to profit (quadratic knapsack problem), or have variable weight which follows a random distribution (stochastic knapsack problem). I have also aware of the previous question 1/0 Knapsack Variation with Weighted Edges, but there is only a very generic answer available, and no answer about what is the name of this knapsack.
One existing solution:
I have also read one approximate solution in a paper about DBMS optimizations, where they group the related items as one combined item for knapsack. If use this technique into our example, the items for knapsack will be a, bc, d, e, therefore there is no more dependencies between any two of these four items. However it is easy to construct an example that does not get optimal result, like when an item with "small weight and benefit" is grouped with another item with "large weight and benefit". In this example, the "small" item should not be selected in solution, but is selected together with the "large" item.
Question:
Is there any kind of efficient solving techniques that can get optimal result, or at least with some error guarantee? Or am I taking the wrong direction for modelling this problem?
513
No, you don't need to sort the weights because every row gives the maximum possible value under the weight limit of that row. The maximum will come in the last column of that row.
6. The 0-1 Knapsack problem can be solved using Greedy algorithm. Explanation: The Knapsack problem cannot be solved using the greedy algorithm.
The 0/1 knapsack problem means that the items are either completely or no items are filled in a knapsack. For example, we have two items having weights 2kg and 3kg, respectively. If we pick the 2kg item then we cannot pick 1kg item from the 2kg item (item is not divisible); we have to pick the 2kg item completely.
Time complexity for 0/1 Knapsack problem solved using DP is O(N*W) where N denotes number of items available and W denotes the capacity of the knapsack.
Could you not have items a, b, c, bc, d and e? Possibly with a constraint that b and bc can't be both in the knapsack and similarly so with c and bc? My understanding is that that would be a correct solution since any solution that has b and c can be improved by substituting both by bc (by definition). The constraints on membership should take care of any other cases.
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
