当前位置：网站首页>Brainstorm: Complete Backpack

Brainstorm: Complete Backpack

2022-08-04 23:43:00 【InfoQ】

Title

There are N items and a backpack that can carry a maximum weight of W.The weight of the ith item is weight[i], and the resulting value is value[i].Each item has an infinite number (that is, it can be put into the backpack multiple times), and find out which items are put into the backpack with the largest sum of item value.

Solution ideas

The only difference between the complete backpack and the 01 backpack problem is that there are infinite pieces of each item. What is the maximum value of the items that the backpack can carry?The difference between solving this problem and the 01 knapsack problem lies in the traversal order.

So the first step is to determine the definition of the dp array. In a one-dimensional dp array, dp[j] means: a backpack with a capacity of j, the value of the items carried can be up to dp[j].

The second step is to determine the recursive formula, dp[j] can be derived from dp[j - weight[i]], dp[j - weight[i]] indicates that the capacity is j -The maximum value carried by the backpack of weight[i].dp[j - weight[i]] + value[i] represents the knapsack with capacity j - the weight of item i plus the value of item i.At this time, dp[j] has two choices, one is to take its own dp[j] which is equivalent to dp[i-1][j] in the two-dimensional dp array, that is, to not put item i, one is to take dp[j -weight[i]] + value[i], i.e. put item i, the designation is to take the largest one, after all, it is to find the largest value, so the recursive formula is: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

The third step is to initialize the dp array. Since the value of the items is greater than 0, the dp arrayWhen initialized, it can be initialized to 0.

We know that the loop embedded in the 01 backpack is traversed from large to small, in order to ensure that each item is only added once.

The items in the complete backpack can be added multiple times, so it is necessary to traverse from small to large. The code is as follows:

// Traverse the items first, thenTraverse backpack
for(int i = 0; i < weight.size(); i++) { // Traverse items
 for(int j = weight[i]; j <= bagWeight ; j++) {// Traverse the knapsack capacity
 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

 }
}

Code Implementation

private static void testCompletePack(){
 int[] weight = {1, 3, 4};
 int[] value = {15, 20, 30};
 int bagWeight = 4;
 int[] dp = new int[bagWeight + 1];
 for (int i = 0; i< weight.length; i++){ // Traverse items
 for (int j = weight[i]; j <= bagWeight; j++){ // Traverse bag capacity
 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
 }
 }
 for (int maxValue : dp){
 System.out.println(maxValue + " ");
 }
}

原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/216/202208042333173801.html