最近为备考NOIP在复习背包模型,发现好多地方对于状态表示的定义存在严重问题。
相信这种表示是常见的:$f[i,j]$表示从前$i$个物品中选出了总体积为$j$的物品放入背包,物品的最大价值和。
这个说法是禁不起推敲的。看看下面这份代码:
#include<bits/stdc++.h>
using namespace std;
int v[105],w[105];
int f[1005];
int main()
{
int t,m;
scanf("%d%d",&t,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=m;i++)
for(int j=t;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d",f[t]);
return 0;
}
423题解答,相信也是绝大多数人的模板。或许大家没有思考为什么直接输出f[t]就是答案。想一想,按照那个状态表示,不应该把所有的体积下的答案都取个最大值再输出吗?这是因为我们的状态表示出了问题!
以$i=1,j=t$时为例,此时的$f[j]$更新为$w[i]$也就是$w[1]$,然而$v[1]$未必等于$t$。所以,状态表示的应为不超过体积$j$的情况下。
如果非要使用原来的状态表示,那么代码应当这么写:
#include<bits/stdc++.h>
using namespace std;
int v[105],w[105];
int f[1005];
int main()
{
int t,m;
scanf("%d%d",&t,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&w[i]);
f[0]=1;
for(int i=1;i<=m;i++)
for(int j=t;j>=v[i];j--)
if(f[j-v[i]])f[j]=max(f[j],f[j-v[i]]+w[i]);
int ans=0;
for(int i=1;i<=t;i++)ans=max(ans,f[i]);
printf("%d",ans-1);
return 0;
}
从而保证了每次都会从一个真实存在的体积转移过来。