背包问题(栈和队列)

背包问题(栈和队列)

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注