题目已经告诉了我们,这道题是背包,而且是01背包
那 01 背包是何方神圣???
我哪知道他是何方神圣,它只是一个正常毒瘤的算法,就是你每个物品要么选,要么不选QWQ
所以第一反应:爆搜
然后一看效率:2^n -> 极限数据的用时为 10^300
一台好的评测机每秒10^9已经十分勉强
所以——TLE++
So,Pass爆搜
所以咱就要用背包
CODE
#include<iostream>
#include<algorithm>
using namespace std;
int n,v,tj[1002],jz[1002],ans[2000002];
int main()
{
cin>>n>>v;
for(int a=0;a<n;a++)cin>>tj[a]>>jz[a];
for(int a=0;a<n;a++)
{
for(int b=v;b>=0;b--)
{
if(ans[b])ans[b+tj[a]]=max(ans[b+tj[a]],ans[b]+jz[a]);
}
ans[tj[a]]=max(ans[tj[a]],jz[a]);
}
int sc=0;
for(int a=0;a<=v;a++)sc=max(ans[a],sc);
cout<<sc<<endl;
return 0;
}
由于我打过模板,没测样例直接交了
Then,0分++
Why?
#include<algorithm>
using namespace std;
int n,v,tj[1002],jz[1002],ans[2000002];
int main()
{
cin>>n>>v;
for(int a=0;a<n;a++)cin>>tj[a]>>jz[a];
for(int a=0;a<n;a++)
{
for(int b=v;b>=0;b--)
{
if(ans[b])ans[b+tj[a]]=max(ans[b+tj[a]],ans[a]+jz[b]);//背包的转移方程
}
ans[tj[a]]=max(ans[tj[a]],jz[a]);
}
int sc=0;
for(int a=0;a<=v;a++)sc=max(ans[a],sc);
cout<<sc<<endl;
return 0;
}
刚刚的一个地方a和b打反了