背包问题 不理解一个IF判断和赋值的语句的意思
int n,m,f[30010],c[30],v[30],jilao[30];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>c[i]>>v[i];
jilao[i]=c[i]*v[i];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=c[i];j--)
if(f[j]<f[j-c[i]]+jilao[i]) // 帮忙解释下IF判断
f[j]=f[j-c[i]]+jilao[i]; // 这里也是不知道什么意思
cout<<f[m]<<endl;
getch();
return 0;
}
[解决办法]
f[j]表示当包是j这么大的时候的最大价值
f[j-c[i]]表示包是j-c[i]的最大价值。此时再放入c[i]大小的物品,那么包大小就是j-c[i]+c[i],价值就为f[j-c[i]+jilao[i];
然后跟之前的f[j]相比较,判断大小。大的再赋值给f[j];
[解决办法]
还要注意for(int j=m;j>=c[i];j--)
j是从大到小,这是为了保证第i个物品只被放入一次。。。
从小到大,是说明这第i个物品可以放无数次。。
[解决办法]
算法这东西自己理解最好,别人说的你很快就忘了,这个算法不难的,你把它一步一步分解为一个个小问题来看就容易多了,或者找支笔在纸上比划一下就明白了,你就把背包的容量当成数组的长度来算,弄几个简单的例子自己试试就很容易弄懂了。