————— the next day —————
— — — — — —
.
Let’s go back to the previous problem. Assume that the backpack has a capacity of 10 and there are 5 items to choose from. The value and weight of each item are shown in the figure below:
Let’s calculate the cost for each item. The result is as follows:
There is no doubt that item 4 has the highest cost performance at this time. We put item 4 into the backpack, and the remaining capacity of the backpack is 8:
We choose item 1 to put into the backpack, and the remaining capacity of the backpack is 4:
Therefore, we choose 0.8 items 5 to put into the backpack, and the remaining capacity of the backpack is 0:
public static void main(String[] args) { int capacity = 10; Int [] weights =,6,3,2,4 {4}; Int [] values = {9,3,1,6,4}; System.out.println(” knapbag Max value: “+ getHighestValue(capacity, weights, values)); } public static double getHighestValue(int capacity, List itemList = new ArrayList<>(); int[] weights,int[] values){List itemList = new ArrayList<>(); for(int i=0; i
In this code, we use a static inner class Item to make it easier to record cost performance, get weight and value information, and sort by cost performance.
Still given a backpack of capacity 10, there are three items to choose from:
This time we have a condition: only the whole item can be selected, not parts of the item.
If we choose the item 1 with the highest cost performance according to the greedy algorithm, then the remaining capacity of the backpack is 4 and there is no room for other items, and the total value at this time is 6:
But does such a choice really maximize the total value? If we do not select item 1, but item 2 and item 3, the remaining capacity is 0 and the total value is 7:
Obviously, 7>6, depending on the greedy algorithm, is not necessarily the global optimal solution.
For 01 backpack problem, we can use dynamic programming algorithm to solve, interested partners can wechat search “programmer small grey”, there is about the dynamic programming algorithm.
