动态规划思想

简介

动态规划思想

例题

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表示表背包容量（列序号）；

表格的值表示：当容量为 j ，且第 i 个物品加入 物品队列时，背包的最大价值；

代码

#include<iostream>
#include<algorithm>
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_weight+1];//辅助数组

//初始化第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–; //循环结束后,i=n,j=max_weight+1,故使用dp[n – 1][max_weight]须自减1
cout << "最大价值时的背包物品为：" << endl;
while (dp[i][j]&&i>=0) {
if (dp[i][j] != dp[i – 1][j]) {
cout << "物品" << i << endl;
j -= w[i]; //装入物品i后背包的最大容量
}
i–; //物品i已经处理完成，接下来讨论物品i-1
}

return 0;
}