目录
2.1我们通过进行遍历i次，与决策j *i次来选择出状态最优解
2.2简单来说，就是f[j]需要用到前面计算的数据已经被无意地篡改了。
前言
记录一下初学算法的灵光
一、什么背包问题
简单来讲，就是把物品放到背包里的动态规划问题。
例：
有 N 件物品和一个容量是 V 的背包。
第 i件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
下面来浅谈一下该种问题的算法分析。
二.01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
2.1我们通过进行遍历i次，与决策j *i次来选择出状态最优解
如果背包容量不够
该决策不变等于上轮决策结果
对应代码：f[i][j] = f[i - 1][j]
当前背包容量够，可以选，因此需要决策选与不选第 i个物品：
选 ：f[i][j] = f[i - 1][j - v[i]] + w[i]
不选：f[i][j] = f[i - 1][j]
我们的决策是如何取到最大价值，因此以上两种情况取 max()
#include <iostream>
using namespace std;
int v[1005];
int w[1005];
int f[1005][1005];
int main()
{
int n, m,i,j;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (i = 1; i <= n; i++)//判断n次
for (j = 1; j <= m; j++)//遍历使用1—m个空间,判断可否存放该次i
if (j < v[i])//该空间大小放不下
f[i][j] = f[i - 1][j];//等于上一次能放下的情况
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//选出上次与这次的大值：f[i-1][j-v[i]]+w[i]存放i剩的空间能放的最大值+本次值
printf("%d", f[n][m]);
}但显而易见，该方法有个小缺点L:二维数组每一次决策（f [ i ][ j ]）都是只与上一组（f [ i -1 ][ j ]）
进行数据使用及比较，这就很容易造成资源内存的浪费
或许，我们可以试着将 f 数组从二维降到一维...
#include <iostream>
using namespace std;
const int N=1000;
int f[N],v[N],w[N];
int main()
{
int m,n,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(j<v[i])
f[j]=f[j];
else
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d",f[m]);
}
高贵的食材往往只需要最朴素的烹饪方式
我们使用了最暴力的方法（唔，看起来还不错）
但当我们真正提交上去却只有大大的
Wrong Answer ！
why？
2.2简单来说，就是f[j]需要用到前面计算的数据已经被无意地篡改了。
在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维
后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用
的是第i轮的状态
例如：
一维状态，第i轮对体积为 3 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。这样计算的话，w[i]就会多次使用，但实际上只需使用一次。
我们就换一个思路：如果我们是逆序（j=m;i>=0;j++），则f[较大体积]更新到f[较小体积]就不会发生篡改的情况了
上代码：
#include <iostream>
using namespace std;
const int N=1005;
int f[N],v[N],w[N];
int main()
{
int m,n,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=n;i++)
for(j=m;j>=1;j--)
if(j<v[i])
f[j]=f[j];
else
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d",f[m]);
}
但,f[i]=f[i]是个冗余的代码，索性直接把if条件摆在for循环中
#include <iostream>
using namespace std;
const int N=1005;
int f[N],v[N],w[N];
int main()
{
int m,n,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=n;i++)
for(j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d",f[m]);
}
2.3 优化输入
我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举
因此我们可以不必开两个数组记录体积和价值，而是边输入边处理
直接去除下边for(i)循环
#include <iostream>
using namespace std;
const int N=1005;
int f[N],v[N],w[N];
int main()
{
int m,n,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
for(j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
printf("%d",f[m]);
}
总结
以上就是今天要讲的内容，本文仅仅简单分析了01背包的算法，作者水平有限，望各位读者海涵与指正。
ps:该题来自Acming