题目描述
设有n件物品，重量分别为w1,w2,w3,…,wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无解。
输入
5 100
77 92
22 22
29 87
50 46
99 90
输出
133
样例输入
8 200
79 83
58 14
86 54
11 79
28 72
62 52
15 48
68 62
样例输出
334
参考代码
#include<stdio.h>
#include<memory.h>
#define MAX 100
int weight[MAX],value[MAX],n,t,sum,visit[MAX];
void dfs(int w,int v,int k)
{
int i;
if(v&&w<t)
if(v>sum)
sum=v;
if(k==n)
return;
for (i=0;i<n;i++)
if(!visit[i])
{
visit[i]=1;
if(w+weight[i]<=t)
dfs(w+weight[i],v+value[i],k+1);
visit[i]=0;
}
}
int main()
{
int i;
scanf("%d %d",&n,&t);
sum=0;
memset(visit,0,sizeof(visit));
for (i=0;i<n;i++)
scanf("%d %d",&weight[i],&value[i]);
dfs(0,0,0);
printf("%dn",sum);
return 0;
}
解析
暂无
