背包问题(栈和队列)
时间： 1ms 内存：1000M
描述：
设有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提示：
参考答案（内存最优[752]）：
#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("%d\n",sum);
return 0;
}
参考答案（时间最优[0]）：
#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("%d\n",sum);
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。