前言
This Series aritcles are all based on the book 《经典算法大全》; 对于该书的所有案例进行一个探究和拓展,并且用python和C++进行实现; 目的是熟悉常用算法过程中的技巧和逻辑拓展。
提出问题
13.Algorithm Gossip:背包问题 ( Knapsack Problem)
说明
假设有一个背包的负重最多可达8公斤,而希望在背包中装入负重范围内可得之总价物品, 假设是水果好了,水果的编号、单价与重量如下所示:
解法
> 背包问题是关于最佳化的问题,要解最佳化问题可以使用「动态规划」(Dynamic programming),从空集合开始,每增加一个元素就先求出该阶段的最佳解,直到所有的元素加入至集合中,最后得到的就是最佳解。以背包问题为例,我们使用两个阵列value与item,value表示目前的最佳解所得之总价,item表示最后一个放至背包的水果,假设有负重量1~8的背包8个,并对每个背包求其最佳解。
Java 实现
class Fruit {
private String name;
private int size;
private int price;
public Fruit(String name,int size, int price){
this.name = name;
this.size = size;
this.price = price;
}
public String getName(){
return name;
}
public int getPrice(){
return price;
}
public int getSize() {
return size;
}
}
public class Knapsack {
public static void main(String[] args){
final int MAX = 8;
final int MIN = 1;
int[] item = new int[MAX+1];
int[] value = new int[MAX+1];
Fruit fruits[] = {
new Fruit("李子 ", 4, 4500),
new Fruit("苹果 ", 5, 5700),
new Fruit("橘子 ", 2, 2250),
new Fruit("草莓 ", 1, 1100),
new Fruit("甜瓜 ", 6, 6700)};
for(int i = 0; i < fruits.length;i++) {
for(int s = fruits[i].getSize(); s <= MAX;s++){
int p = s - fruits[i].getSize();
int newvalue = value[p] +
fruits[i].getPrice();
if(newvalue > value[s]) {// 找到阶段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
System.out.println("物品 价格");
for(int i = MAX;
i >= MIN;
i = i - fruits[item[i]].getSize()) {
System.out.println(fruits[item[i]].getName()+
" " + fruits[item[i]].getPrice());
}
System.out.println("合计 " + value[MAX]);
}
}
拓展和关联
01 背包有两类问题, 主要是 DP 问题, 以后设定专题详解, 贪心算法本质是只是最优子结构不具备无后效性。 是一种特殊的动态规划
后记
参考书籍
- 《经典算法大全》
- 维基百科