“背包DP代码”版本间的差异
来自iCenter Wiki
（以“#include<cstdio> #include<algorithm> using namespace std; const int N=1e3+1; int n,m,v[N],c[N]; //从第i个物品开始挑选总重量不大于sumv的部分 int d...”为内容创建页面） |
|||
| 第6行： | 第6行： | ||
//从第i个物品开始挑选总重量不大于sumv的部分 | //从第i个物品开始挑选总重量不大于sumv的部分 | ||
int dfs(int now,int 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(){ | 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; | |
} | } | ||
2019年5月10日 (五) 10:22的版本
- 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; }
