动态规划-0-1背包问题
动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，由美国数学家 Bellman 等人在1957年提出，用于研究多阶段决策过程的优化问题。
[toc]
动态规划适合的问题（最优解）
动态规划法适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，这些问题必须满足最优化原理和子问题的“无后向型”。
动态规划的基本步骤
一般需要四个步骤;
st=>start: 定义最优子问题
e=>end: 确定边界条件
op1=>operation: 定义状态
op2=>operation: 定义决策和状态转换方程
st->op1->op2->e
0-1背包问题
有一个背包,承载量为 C,现有 n 个物品,其中物品 i (0< i <=n) 重量为 wi,价值为pi, 现在从 n 个物品里选择一个或多个装入背包,要求在物品总重量不超过 C 的前提下,所装入的物品价值最高.
1.定义最优子问题
每选择一个物品就可以看做一个阶段,其子问题就可以定义成每次向包里装入一个物品,直到超过背包最大容量为止.
2.定义状态
在满足"无后向性"要求下,定义问题的状态: s[i, j] 将第 i 件物品装入容量为 j 的包里所能获得的最大价值.
3.定义决策和状态转换方程
- 决策:判断装入 第 i 件物品的总价值和不装入第 i 件物品的总价值哪个更大.
如果不装入第 i 件物品,则背包内物品的价值仍然是 s[i-1, j];
如果装入第 i 件物品,则背包内物品的价值就是 s[i-1, j-wi]+pi. - 状态转换方程:s[i, j] = max(s[i-1, j], s[i-1, j-w_i]+p_i)
4.确定边界条件
边界条件就是没有装入任何物品的状态:s[0, j] = 0
5.递归写法
#include <iostream>
#include <algorithm>
using namespace std;
int q[6] = {0,3, 6, 5, 4, 6}; // 价值
int t[6] = {0,2, 4, 6, 5, 2}; // 重量
int V = 2; // 背包容量
int func(int i, int V); // i 个物品, 背包容量 V
int main(int argc, char *argv[]) {
int highest = func(5, V);
cout << "最高价值：" << highest << endl;
return 0;
}
int func(int i, int V){
if(i == 0 || V == 0) {
return 0;
}else if (V>=t[i]){
return max(func(i-1, V), func(i-1, V-t[i])+q[i]);
}else{
return func(i-1, V);
}
}
6.状态表(备忘录)写法
#include <iostream>
using namespace std;
int q[6] = {0,3, 6, 5, 4, 6}; // 价值
int t[6] = {0,2, 4, 6, 5, 2}; // 重量
int V = 10; // 背包容量
int main(int argc, char *argv[]) {
int f[6][V+1]; // 状态表
// 初始化边界条件
for (int i = 0; i < 6; i++){
f[i][0] = 0;
f[0][i] = 0;
}
for (int i = 1; i < 6; i++){
for (int j = 1; j < V+1; j++){
if(j >= t[i]){
f[i][j] = max(f[i-1][j], f[i-1][j-t[i]]+q[i]);
}else{
f[i][j] = f[i-1][j];
}
}
}
// 打印状态表
for (int i = 0; i < 6; i++){
for (int j = 0; j < V+1; j++){
cout << f[i][j] << " ";
}
cout << endl;
}
return 0;
}
