Comics: What is the "Greedy Algorithm"? How to solve the "partial backpack problem"?

————— Day 2 —————

————————————

. . . . . . . .

Let's go back to the previous topic, suppose the capacity of the backpack is 10, there are 5 items to choose from, and the value and weight of each item are shown in the figure:

Let's calculate the price/performance ratio for each item, and the result is as follows:

Undoubtedly, the most cost-effective item at this time is item 4, we put item 4 into the backpack, and the remaining capacity of the backpack is 8:

We select item 1 to put into the backpack, the remaining capacity of the backpack is 4:

So, we choose 0.8 portions of item 5 into the backpack, the remaining capacity of the backpack is 0:

public static void main(String[] args) {

int capacity = 10;

int[] weights = {4,6,3,2,4};

int[] values = {9,3,1,6,4};

System.out.println ("backpack max value:"+ getHighestValue(capacity, weights, values));

}

public static double getHighestValue(int capacity, int[] weights,int[] values){

Create an item list and follow the price/performance ratio in reverse order

List<Item> itemList = new ArrayList<>();

for(int i=0;i<weights.length;i++){

itemList.add(new Item(weights[i], values[i]));

itemList = itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());

Remaining capacity of the backpack

int restCapacity = capacity;

The maximum value of the current backpack item

double highestValue = 0;

Choose items from high to low according to the value for money

for(Item item : itemList){

if(item.weight <= restCapacity){

highestValue += item.value;

restCapacity -= item.weight;

}else{

When the back pack cannot fit the complete item, select a portion of the item

highestValue += (double)restCapacity / (double)item.weight * item.value;

break;

return highestValue;

static class Item {

private int weight;

private int value;

Value for money for items

private double ratio;

public Item (int weight, int value){

this.weight = weight;

this.value = value;

this.ratio = (double)value / (double)weight;

public double getRatio() {

return ratio;

In this code, we use static internal class Items to make it easier to record price/performance, obtain weight and value information, and sort by price/performance.

Still given a backpack with a capacity of 10, there are three items to choose from:

This time we have a conditional restriction: only the entire item is allowed to be selected, not a part of the item.

If according to the idea of the greedy algorithm, the first choice is the most cost-effective item 1, then the remaining capacity of the backpack is 4, and no other items can be filled, and the total value at this time is 6:

But can such a choice really maximize the total value? If we do not select item 1, item 2 and item 3, the remaining capacity is 0 and the total value is 7:

Obviously, 7>6, relying on the greedy algorithm to obtain the result, is not necessarily the global optimal solution.

For the 01 backpack problem, we can use the dynamic programming algorithm to solve, interested partners can weChat search for "programmer's little gray", which has an explanation of the dynamic programming algorithm.