简介动态规划思想例题0-1背包特点每种物品都只有一件可以选择放入或不放入思路使用2~n维数据记录子问题的解建立子问题之间的联系类似斐波那契数列问题分析确定备忘录的具体含义设二维数组 dp[i][j] dp[i][j]:任取第0~i件物品放入容量为j的背包能得到的最大价值 例dp[1][2]3的含义: 任取物品0~物品1放入容量为2的背包能得到的最大价值取物品1放入背包其价值最大为3对于第 i 个物品它只有放与不放两种状态当它能放入背包时状态转移方程只需取两种状态的最大值; 否则取不放入时的最大价值。状态方程// 背包容量小于物品重量 取不放入物品最大值 if (j w[i]) dp[i][j] dp[i - 1][j]; else // 当第 i 个物品能够放入时最大价值为背包剩余容量的最大价值 加上 第 i 个物品的价值 // 将第 i 个物品放入的最大价值 与 不放入的最大价值想比较 取最大值 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]);例题题目有n个物品和一个容量为C的背包。每个物品i都有重量w[i]和价值v[i]其中1 ≤ i ≤ n。需要选择一些物品放入背包使得放入的物品总重量不超过背包容量C且总价值最大。输入// n表示物品索引w[n]与v[n]分别表示在索引为n时物品的重量为w[n]价值为v[n]; 1. int w[n] { 2,1,4,3 }; //重量 2. int v[n] { 4,3,6,5 }; //价值结题思路i表示物品索引行序号j表示表背包容量列序号i \ j0123450004444103477720347793034789表格的值表示当容量为 j 且第 i 个物品加入 物品队列时背包的最大价值代码#includeiostream #includealgorithm using namespace std; const int max_weight 5; const int n 4; int main() { int i, j; int w[n] { 2,1,4,3 }; //重量 int v[n] { 4,3,6,5 }; //价值 int dp[n][max_weight1];//辅助数组 //初始化第0列即背包容量为0 for (i 0; i n; i) dp[i][0] 0; //初始化第0行即只有物品0 for (j 1; j max_weight; j) { if (w[0] j) dp[0][j] v[0]; else dp[0][j] 0; } //状态转移 //先遍历物品再遍历背包 for (i 1; i n; i) { //遍历物品 for (j 1; j max_weight; j) { //遍历背包 if (j w[i]) dp[i][j] dp[i - 1][j]; else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]); } } //输出 cout dp[n - 1][max_weight] endl; //回溯法求解装入物品 i--; j--; //循环结束后,in,jmax_weight1,故使用dp[n - 1][max_weight]须自减1 cout 最大价值时的背包物品为 endl; while (dp[i][j]i0) { if (dp[i][j] ! dp[i - 1][j]) { cout 物品 i endl; j - w[i]; //装入物品i后背包的最大容量 } i--; //物品i已经处理完成接下来讨论物品i-1 } return 0; }
)
