40.讲初识动态规划:如何巧妙解决“双十一”购物时的凑单问题
文章目录
- 1. 动态规划学习路线
- 2. 0-1背包问题
- 3. 0-1背包问题升级版
问题: 满200元减50元”。购物车中有n个(n>100)想买的商品,希望从里面选几个,在凑够满减条件的前提下,让选出来的商品价格总和最大程度地接近满减条件(200元),如何解决?
1. 动态规划学习路线
- 初识动态规划
通过两个非常经典的动态规划问题模型,认识为什么需要动态规划,动态规划解决方法如何演化。
- 动态规划理论
总结动态规划适合解决的问题的特征,以及动态规划解题思路。除此之外,将贪心、分治、回溯、动态规划这四种算法思想放在一起,对比分析它们各自的特点以及适用的场景。
- 动态规划实战
实战解决三个非常经典的动态规划问题。
2. 0-1背包问题
// 回溯算法实现。注意:我把输入的变量都定义成了成员变量。
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2,2,4,6,3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw) { // 调用f(0, 0)
if (cw == w || i == n) { // cw==w表示装满了,i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
}
f(i+1, cw); // 选择不装第i个物品
if (cw + weight[i] <= w) {
f(i+1,cw + weight[i]); // 选择装第i个物品
}
}
找规律:
重复解:
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2,2,4,6,3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录,默认值false
public void f(int i, int cw) { // 调用f(0, 0)
if (cw == w || i == n) { // cw==w表示装满了,i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
}
if (mem[i][cw]) return; // 重复状态
mem[i][cw] = true; // 记录(i, cw)这个状态
f(i+1, cw); // 选择不装第i个物品
if (cw + weight[i] <= w) {
f(i+1,cw + weight[i]); // 选择装第i个物品
}
}
二维数组states[n][w+1],来记录每层可以达到的不同状态。
weight:物品重量,n:物品个数,w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
boolean[][] states = new boolean[n][w+1]; // 默认值false
states[0][0] = true; // 第一行的数据要特殊处理,可以利用哨兵优化
states[0][weight[0]] = true;
for (int i = 1; i < n; ++i) { // 动态规划状态转移
for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
if (states[i-1][j] == true) states[i][j] = states[i-1][j];
}
for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
if (states[i-1][j]==true) states[i][j+weight[i]] = true;
}
}
for (int i = w; i >= 0; --i) { // 输出结果
if (states[n-1][i] == true) return i;
}
return 0;
}
优化:boolean[][] states是二维,比较耗内存,可以用一维替代
public static int knapsack2(int[] items, int n, int w) {
boolean[] states = new boolean[w+1]; // 默认值false
states[0] = true; // 第一行的数据要特殊处理,可以利用哨兵优化
states[items[0]] = true;
for (int i = 1; i < n; ++i) { // 动态规划
for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包
if (states[j]==true) states[j+items[i]] = true;
}
}
for (int i = w; i >= 0; --i) { // 输出结果
if (states[i] == true) return i;
}
return 0;
}
3. 0-1背包问题升级版
刚刚讲的背包问题,只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品装入背包,在满足背包最大重量限制的前提下,背包中可装入物品的总价值最大是多少呢?
- 回溯
private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] items = {2,2,4,6,3}; // 物品的重量
private int[] value = {3,4,8,9,6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
if (cw == w || i == n) { // cw==w表示装满了,i==n表示物品都考察完了
if (cv > maxV) maxV = cv;
return;
}
f(i+1, cw, cv); // 选择不装第i个物品
if (cw + weight[i] <= w) {
f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品
}
}
public static int knapsack3(int[] weight, int[] value, int n, int w) {
int[][] states = new int[n][w+1];
for (int i = 0; i < n; ++i) { // 初始化states
for (int j = 0; j < w+1; ++j) {
states[i][j] = -1;
}
}
states[0][0] = 0;
states[0][weight[0]] = value[0];
for (int i = 1; i < n; ++i) { //动态规划,状态转移
for (int j = 0; j <= w; ++j) { // 不选择第i个物品
if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
}
for (int j = 0; j <= w-weight[i]; ++j) { // 选择第i个物品
if (states[i-1][j] >= 0) {
int v = states[i-1][j] + value[i];
if (v > states[i][j+weight[i]]) {
states[i][j+weight[i]] = v;
}
}
}
}
// 找出最大值
int maxvalue = -1;
for (int j = 0; j <= w; ++j) {
if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
}
return maxvalue;
}
时间复杂度是O(nw),空间复杂度也是O(nw)。