讨论 / 0-1背包问题
WKSFFF 2018-06-17 17:13:21
点我顶贴 收藏 删除
#include<cstdio>

#include<algorithm>

#define maxn 20035

using namespace std;

int main(){

int V,n;

scanf("%d%d",&V,&n);

int v[35];

for(int i=1;i<=n;i++)

scanf("%d",&v[i]);

int f[maxn];

for(int i=1;i<=n;i++)

f[n]=0;

for(int i=1;i<=n;i++)

for(int j=V;j>=v[i];j--){

if(f[j-v[i]]+v[i]<=V)

f[j]=max(f[j],f[j-v[i]]+v[i]);

}

printf("%d\n",V-f[V]);

return 0;

}

查看更多回复
提交回复