一、介绍 1) 动态规划 ( Dynamic Programming ) 算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 ● 2) 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 ● 3) 与分治法不同的是, 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 ) ● 4) 动态规划可以通过 填表的方式 来逐步推进,得到最优解 .
二、动态规划算法最佳实践-背包问题
背包问题:有一个背包,容量为4磅 , 现有如下物品
| 物品 | 重量 | 价格 |
| Uzi | 1 | 1500 |
| 98K | 4 | 3000 |
| Akm | 3 | 2000 |
(1) v[ i ][0]=v[0][j]=0; // 表示 填入表 第一行和第一列是 0
(2) 当w[i]> j 时:v[i][j]=v[i-1][j]
// 当准备加入新增商品的容量大于 当前背包的容量时,就直接使用上一个单元格的装入策略
(3) 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
// 当 准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:先把新的装进去,如果有剩余空间的话尽可能装价值大的
v[i-1][j]: 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] : 装入i-1商品,到剩余空间j-w[i]的最大值
当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :
三、代码演示1.物品类
class thing{
private String name;//物品名字
private int weight;//物品重量
private int value;//物品价值
public thing(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
@Override
public String toString() {
return name + " " + weight+ " " + value;
}
}
2.主程序
public static void main(String[] args) {
int maxVolume = 8;//背包容量:8
//物品栏
List items = new ArrayList<>();
items.add(new thing("000", 0, 0));//用来占位置的,没实际意义
items.add(new thing("Uzi", 1, 1500));
items.add(new thing("98k", 4, 3000));
items.add(new thing("Akm", 3, 2000));
//先看下物品栏有哪些东西
System.out.println("物品 重量 价格");
for (thing e : items) System.out.println(e);
System.out.println();
//对于不同物品、不同背包容量,能够装入背包的物品的最大价值
int[][] values = new int[items.size()][maxVolume+1];
//初始化.第一列/行置0
for (int i = 0; i < items.size(); i++) values[i][0] = 0;
for (int i = 0; i < maxVolume+1; i++) values[0][i] = 0;
//依次看装入(1),(1、2),(1、2、3)这几个物品时的情况
for (int itemIndex = 1; itemIndex < items.size(); itemIndex++) {
//依次看不同背包容量下的情况(1~8)
for (int volume = 1; volume < maxVolume+1; volume++) {
//1、如果准备加入的新物品容量比背包容量大,装不下新物品,
//就使用同背包容量上次的装入策略
if (items.get(itemIndex).getWeight() > volume) values[itemIndex][volume] = values[itemIndex - 1][volume];
//2、否则就有两种情况
//2.1 加入新物品后,新物品价值加上剩余空间所放旧物品的最高价值
//比同背包容量上个装入策略的总价值要高,那我们就使用新的策略
else if (values[itemIndex - 1][volume] < items.get(itemIndex).getValue() + values[itemIndex - 1][volume - items.get(itemIndex).getWeight()]) {
values[itemIndex][volume] = items.get(itemIndex).getValue() + values[itemIndex - 1][volume - items.get(itemIndex).getWeight()];
}
//2.2 否则还使用原来的策略。
else {
values[itemIndex][volume] = values[itemIndex - 1][volume];
}
}
}
//看一下values 目前的情况,打印成表格
System.out.print("物品/容量 ");
for (int i = 1; i < maxVolume+1; i++) System.out.print(i + " ");
System.out.println();
for (int i = 1; i < items.size(); i++) {
System.out.print(items.get(i).getName() + " ");
for (int j = 1; j < maxVolume+1; j++) {
System.out.print(values[i][j] + " ");
}
System.out.println();
}
}
3.测试
物品 重量 价格 000 0 0 Uzi 1 1500 98k 4 3000 Akm 3 2000 物品/背包容量 1 2 3 4 5 6 7 8 Uzi 1500 1500 1500 1500 1500 1500 1500 1500 98k 1500 1500 1500 3000 4500 4500 4500 4500 Akm 1500 1500 2000 3500 4500 4500 5000 6500



