@[蒟蒻chi_chi](/space/show?uid=31728) 有一道和这个一样的题,叫采药,可以看看我写的题解
by decoqwq @ 2018-02-20 14:39:50
@[蒟蒻chi_chi](/space/show?uid=31728) https://www.luogu.org/blog/48265/solution-p1048
by decoqwq @ 2018-02-20 14:40:15
@[蒟蒻chi_chi](/space/show?uid=31728) 至于你这个方法的问题,你可以想个例子,比如说我有三个物品,重量分别是6 4 5,价值分别是 12 7 9,背包空间为9,按你的方法优先选择了一号物品就装不下了,而选择二号和三号明显优于只选一号,你的方法问题就出在这
by decoqwq @ 2018-02-20 14:43:04
@[刘浩宇(寂)](/space/show?uid=48265) 哦哦!谢谢指导,我再去想想。
by si_zhong @ 2018-02-20 20:11:38
$x^q \equiv p \pmod f
by decoqwq @ 2018-02-20 21:07:17
同志,对于这种题目应该用一种叫做动态规划的算法而不是这种叫做贪心的算法。
上~~AC~~代码
#include<bits/stdc++.h>
using namespace std;
int v,n,w[3403],c[3403],opt[12881];
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=v;j>=w[i];j--)
opt[j]=max(opt[j-1],opt[j-w[i]]+c[i]);
cout<<opt[v]<<endl;
return 0;
}//其实我也不知道发生了什么
by yy233 @ 2018-03-17 18:15:37
@[yy233](/space/show?uid=50321) orz
by rgq233666 @ 2018-04-26 17:14:43
@[rgq233666](/space/show?uid=33399) ```cpp
#include<bits/stdc++.h>
using namespace std;
int v,n,w[3403],c[3403],opt[12881];
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=v;j>=w[i];j--)
opt[j]=max(opt[j-1],opt[j-w[i]]+c[i]);
cout<<opt[v]<<endl;
return 0;
}
```
by yy233 @ 2018-04-29 14:41:34
@[yy233](/space/show?uid=50321) 大佬orz,但是您不会用代码模板吗???
by TianZ @ 2018-05-07 12:37:41
@[天真、陈长生](/space/show?uid=67212) 我不知我代码模板在这里发生了什么
by yy233 @ 2018-05-08 09:27:16