“背包DP代码”版本间的差异
来自iCenter Wiki
| 第1行： | 第1行： | ||
| − | #include<cstdio> | + | #include<cstdio> |
| − | #include<algorithm> | + | #include<algorithm> |
| − | using namespace std; | + | using namespace std; |
| − | const int N=1e3+1; | + | const int N=1e3+1; |
| − | int n,m,v[N],c[N]; | + | int n,m,v[N],c[N]; |
| − | //从第i个物品开始挑选总重量不大于sumv的部分 | + | //从第i个物品开始挑选总重量不大于sumv的部分 |
| − | int dfs(int now,int sumv){ | + | int dfs(int now,int sumv){ |
| − | int res; | + | int res; |
| − | if(now==n+1) return res=0;//已经没有剩余物品 | + | if(now==n+1) return res=0;//已经没有剩余物品 |
| − | if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品 | + | if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品 |
| − | else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况 | + | else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况 |
| − | return res; | + | return res; |
| − | } | + | } |
| − | int main(){ | + | int main(){ |
| − | scanf("%d%d",&m,&n); | + | scanf("%d%d",&m,&n); |
| − | for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]); | + | for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]); |
| − | printf("%d",dfs(1,m)); | + | printf("%d",dfs(1,m)); |
| − | return 0; | + | return 0; |
| − | } | + | } |
2019年5月10日 (五) 10:23的最后版本
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N];
//从第i个物品开始挑选总重量不大于sumv的部分
int dfs(int now,int sumv){
int res;
if(now==n+1) return res=0;//已经没有剩余物品
if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品
else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况
return res;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
printf("%d",dfs(1,m));
return 0;
}
