### 算法入门教程

JdreamZhang · 更新于 2020-07-14

# 贪心算法之背包问题

## 3. 贪心算法求解背包问题

``````unitValue(1) = 20/10 = 2
unitValue(2) = 30/5  = 6
unitValue(3) = 15/15 = 1
unitValue(4) = 25/10 = 2.5
unitValue(5) = 10/20 = 0.5
``````

``````unitValue(2) > unitValue(4) > unitValue(1) > unitValue(3) > unitValue(5)
``````

2 5 5 25
4 10 15 15
1 10 25 5
3 5 30 0

## 4.JAVA 代码实现

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Knapsack {

/**
* 物品内部类
*/
private static class Item implements Comparable<Item>{
int type;
double weight;
double value;
double unitValue;

public Item(int type, double weight){
this.type = type;
this.weight = weight;
}

public Item(int type, double weight,double value){
this.type = type;
this.weight = weight;
this.value = value;
this.unitValue = value/weight;
}

@Override
public int compareTo(Item o) {
return Double.valueOf(o.unitValue).compareTo(this.unitValue);
}
}

public static void main(String[] args){
//背包容量
double capacity = 30;
//物品类型初始化数组
int[] itemType = {1,2,3,4,5};
//物品重量初始化数组
double[] itemWeight = {10,5,15,10,30};
//物品价值初始化数组
double[] itemValue = {20,30,15,25,10};

//初始化物品
List<Item> itemList = new ArrayList<>();
for(int i=0;i<itemType.length;i++){
Item item = new Item(itemType[i],itemWeight[i],itemValue[i]);
}
//物品按照单价降序排序
Collections.sort(itemList);

//背包选择
List<Item> selectItemList = new ArrayList<>();
double selectCapacity = 0;
for(Item item : itemList){
if( (selectCapacity + item.weight) <= capacity){
selectCapacity = selectCapacity + item.weight;
Item selectItem = new Item(item.type,item.weight);
}else {
Item selectItem = new Item(item.type, capacity-selectCapacity);
break;
}
}

//选择结果输出
for (Item item : selectItemList){
System.out.println("选择了类型："+ item.type+" 的物品，重量为："+item.weight);
}

}
}
``````

``````选择了类型：2 的物品，重量为：5.0

``````