记忆搜索与动态规划——DP背包问题
题目描述
01背包问题
有n个重量和价值分别为$w_i,v_i$的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值中总和的最大值。
限制条件
- 1 ⇐ n ⇐ 100
- 1 ⇐ w_i,v_i ⇐ 100
- 1 ⇐ W ⇐ 10000
样例输入
n = 4
(w,v) = {(2,3) (1,2) (3,4) (2,2)}
W = 5
样例输出
7(选择0,1,3号物品)
暴力求解
# include <iostream>
# include <algorithm>
using namespace std;
int n, W;
const int MAX_N = 10000;
int w[MAX_N], v[MAX_N];
int rec(int i, int j)
{
int res;
if (i == n)
{
res = 0;//在递归中,这也就相当于是循环的终止条件了
}
else if (j < w[i])//无法挑选物品
{
res = rec(i + 1, j);//采用递归的方法,对下一个物品进行挑选
}
else//挑选和不挑选都尝试一下
{
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
//第一个是不挑选的情况
//对于挑选的情况,因为采用了递归的方式,j 最为各个物品之间的和,每次当然要减去
//挑选出来的满足条件的上一个物品的重量,并且对于挑选出的满足条件的物品的价值进行相加
}
return res;
}
void solve()
{
printf("%d\n", rec(0, W));//一直到i == 0,则退出递归输出结果
}
int main()
{
cin >> n;
cout << "输入每个物品的重量";
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
cout << "输入每个物品的价值";
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
cout << "输入不能超过的最大的重量";
cin >> W;
solve();
return 0;
}
小结
- 对于这一段代码,rec(i + 1, j – w[i]) + v[i] 尤其是对于这个可以挑选的这一段代码
的解释,想了一一下,一开始是有一个j 作为标准,从第i个物品开始挑选重量 小于j的物品,如果挑选出
来一个这样的物品了,那么再挑选下一个物品的时候就必须要把前一个物品的重量减去,然后以这个新的
“重量”来挑选下一个物品,为什么要这样做呢,原因很简单,因为是要求挑选出的物品总重量必须不能超过
W 的物品的重量。当然了,对于没有挑选出来的,根本也就不存在价值的可能。不用相加。 - 对于递归其实在某种意义上市一种循环,只是循环的条件有所不同。
利用记忆化数组来降低时间复杂度
# include <iostream>
# include <algorithm>
using namespace std;
int n, W;
const int MAX_N = 10000;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_N+1];//记忆化数组
int rec(int i, int j)
{
if (dp[i][j] >= 0)
{
return dp[i][j];//已经计算过的话直接使用之前的结果
}
int res;
if (i == n)
{
res = 0;//在递归中,这也就相当于是循环的终止条件了
}
else if (j < w[i])//无法挑选物品
{
res = rec(i + 1, j);//采用递归的方法,对下一个物品进行挑选
}
else//挑选和不挑选都尝试一下
{
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
//第一个是不挑选的情况
//对于挑选的情况,因为采用了递归的方式,j 最为各个物品之间的和,每次当然要减去
//挑选出来的满足条件的上一个物品的重量,并且对于挑选出的满足条件的物品的价值进行相加
}
return dp[i][j] = res;//将结果记录在数组中
}
void solve()
{
memset(dp, -1, sizeof(dp));//用-1 表示尚未计算过,初始化整个数组
printf("%d\n", rec(0, W));//一直到i == 0,则退出递归输出结果
}
int main()
{
cin >> n;
cout << "输入每个物品的重量";
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
cout << "输入每个物品的价值";
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
cout << "输入不能超过的最大的重量";
cin >> W;
solve();
cin.get();
cin.get();
return 0;
}
DP 利用动态规划解决01 背包
在我的理解里,动态规划,所谓动态,就是各个状态都是时刻变化的,就如同这个‘01’背包问题。
递推公式
dp[i][j] = 0
\begin{cases}
dp[i+1][j], & \text{(j$\lt$w[i])} \\\
max(dp[i+1][j],dp[i+1][j-w[i]+v[i]]), & \text{(其他)}
\end{cases}
这个的空间复杂度是$O(nW)$ ,对于空间复杂度的计算,对于本例而言 一共有两个for循环 一个for循环中循环了n次,第二个for循环 W 次,那么复杂度就是 nw (如果有多个for的话,就应该接着相乘)
# include <iostream>
# include <algorithm>
using namespace std;
int n, W;
const int MAX_N = 10000;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_N + 1];//dp 数组
void solve()
{
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j <= W; 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]);
}
}
}
printf("%d\n", dp[0][W]);
}
int main()
{
cin >> n;
cout << "请输入每个物品的重量";
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
cout << "请输入每个物品的价值";
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << "请输入不能超过的最大重量";
cin >> W;
solve();
cin.get();
cin.get();
}