正序的话f[j-w[i]]已经在f[j]之前计算过1..i件中的最优值,再计算的话就会出现一种物品选多次的情况
by IntrepidStrayer @ 2020-03-31 10:30:39
你说的是哪种背包?0/1 完全?
by 空无一人 @ 2020-03-31 10:31:23
```
#include <bits/stdc++.h>
using namespace std;
long long f[1000005]={0},a[1000005],b[1000005];
int main()
{
int n,j,i,k,t=0,s,m;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
for(i=1;i<=n;i++)
{
cin>>b[i];
}
for(i=1;i<=n;i++)
{
for(j=m;j>=a[i];j--)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[m];
}
```
by 空无一人 @ 2020-03-31 10:31:40
这是0/1背包的
by 空无一人 @ 2020-03-31 10:32:00
采药这道题不用一维,二维也可以通过的
by 空无一人 @ 2020-03-31 10:33:54
@[panenxuDD](/user/333639) 对对对就是01背包,我见过模板是这样写的,但我不知道为什么这样写哭了
by Thir @ 2020-03-31 10:34:29
你背出这个模板就可以啦!!!
by 空无一人 @ 2020-03-31 10:39:57
https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti
这篇我觉得讲得挺好的
by dhzzhsw @ 2020-03-31 10:54:57
@[luogeJing](/user/303782) 在?
by __gcd @ 2020-03-31 11:22:15
打个比方,假如一个物品重量为 $5$,价值为 $w$ 背包容量为 $10$,那么
$$dp_5=\max(dp_5,dp_0+w)$$
$$dp_{10}=\max(dp_{10},dp_5+w)$$
所以这个物品可能被放了两次
by __gcd @ 2020-03-31 11:25:29