未优化版本
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int n,m;
int main()
{
cin >> n >> m;
for(int i =1; i <= n; i ++)
cin >> v[i] >> w[i];
for(int i=1; i <= n; i++)//i遍历的是现有的物品
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i-1][j];//当前背包装不下第i个候选物品,那么价值就等于前面i-1个物品
if(j >= v[i])//装得下的情况
f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);//在装得下和装不下之间取最大值
}
cout << f[n][m];
return 0;
}
- 一点点个人理解:
f[i-1][j-v[i]]
指的是 上一层,在当前背包大小的前提条件下 留下候选物品 i 的空位之后所能装的最大值。
此时再加上候选物品i的价值就相当于选了候选物品 i 。
优化版本:
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
- 关于遍历j为什么是倒序而不是顺序的问题:
看了很多博客,看到有个博客打了个表自己在纸上画了一下稍微能明白了:
(https://www.cnblogs.com/lanhj/archive/2012/12/05/2802437.html)
我的理解是 每次到满足j >=v[i]
时,你要将候选物品i放进去,那你必须先留下它的位置。所以有j-v[i]
,
通常这时候就要用到前面比较小的空间的价值。
比如第i个物品大小是3,你现在j的容量是7,那你要空出一个3的位置来放i,你就要先回去找前面背包空间等于4的那时候背包的价值,再加上第i个大小为3的候选物品的价值,来更新当前的f[i][j]
。
假设我们j此时是顺序,从小到大遍历,那么在同一个i内,小容量已经遍历更新过了,那后面大容量的时候要用到小容量的值(参考上述例子),就会出错。所以才会有说“此时小容量的价值是第i层而不是第i-1层”。
但如果我们的j是逆序,从大到小遍历,则有先更新大容量的值,再更新小容量的值。这时候,因为先更新大的,那么在同一个i层,小容量的值还没更新,就还是上一层(i-1)的值,加上就不会出错。与二维的时候等价。