0-1背包问题

0-1背包问题

时间: 1ms        内存:128M

描述:

 试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i 的重量是wi ,其价值为vi ,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有2 种选择,即装入背包或不装入背包。不能将物品i 装入背包多次,也不能只装入部分的物品i。

输入:

第一行有2个正整数n和c。n是物品数,c是背包的容量。接下来的1 行中有n个正整数,表示物品的价值。第3 行中有n个正整数,表示物品的重量。

输出:

将计算出的装入背包物品的最大价值和最优装入方案输出。第一行输出为:Optimal value is

示例输入:

5 10
6 3 5 4 6
2 2 6 5 4

示例输出:

Optimal value is
15
1 1 0 0 1

提示:

参考答案(内存最优[1092]):

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int sta;
    int h;
    int v;
    double one_v;
    int nu;
}WU;
int main()
{
    WU num[100],mid;
    int a,b;
    int i;
    scanf("%d %d",&a,&b);
    for(i=0;i<a;i++)
    {
        num[i].nu=i;
        scanf("%d",&num[i].v);
        num[i].sta=0;
    }
    for(i=0;i<a;i++)
    {
        scanf("%d",&num[i].h);
        num[i].one_v=(double)num[i].v/num[i].h;
    }
    int sum=0;
    int j;
    for(i=0;i<a-1;i++)
    {
        for(j=0;j<a-1-i;j++)
        {
            if(num[j].one_v>num[j+1].one_v)
            {
               mid=num[j];
               num[j]=num[j+1];
               num[j+1]=mid;
            }
        }
    }
    i=a-1;
    int sum_v=0;
    while(sum<=b&&i>=0)
    {
        if(sum<=b&&sum+num[i].h<=b)
        {
            sum+=num[i].h;
            num[i].sta=1;
            sum_v+=num[i].v;
        }
        i--;
    }
    printf("Optimal value is\n");
    printf("%d\n",sum_v);
     for(i=0;i<a-1;i++)
    {
        for(j=0;j<a-1-i;j++)
        {
            if(num[j].nu>num[j+1].nu)
            {
               mid=num[j];
               num[j]=num[j+1];
               num[j+1]=mid;
            }
        }
    }
    for(i=0;i<a;i++)
        printf("%d ",num[i].sta);
    return 0;
}

参考答案(时间最优[0]):

#include <iostream> 
using namespace std;
int main()
{
	int n;
	double MAX;
	double ba[100][4];
	double read[100][3];
	double cost;
	double temp[3];
	while(cin>>n>>MAX)   //第一行  输入 货物数量   最大载重 
	{	
		cost=0;
		int i,k,j;
			for(i=0;i<n;i++)
		{
			cin>>ba[i][1];
			read[i][1]=ba[i][1];
		}
		for(i=0;i<n;i++)
		{
			cin>>ba[i][0];
			read[i][0]=ba[i][0];
		}
		for(i=0;i<n;i++)
		{								   // 输入没件货物的重量 和 价值
			ba[i][2]=ba[i][1]/ba[i][0];       //单位货物的价值
		}
		k=n/2;
		while(k!=0)              // 排序
		{	
			for(i=k;i<n;i++)
			{
			temp[0]=ba[i][0];
			temp[1]=ba[i][1];
			temp[2]=ba[i][2];
			for(j=i-k;j>=0&&ba[j][2]>temp[2];j-=k)
			{
				ba[j+k][2]=ba[j][2];
				ba[j+k][1]=ba[j][1];
				ba[j+k][0]=ba[j][0];
			}
			ba[j+k][2]=temp[2];
			ba[j+k][1]=temp[1];
			ba[j+k][0]=temp[0];
			}
			k/=2;
		}
		int z=0;
		for(i=n-1;i>=0;i--)
		{
			if(ba[i][0]<=MAX)
			{
				cost+=ba[i][1];
				MAX-=ba[i][0];
				ba[i][3]=1;
			}
		}
		cout<<"Optimal value is"<<endl;
		cout<<cost<<endl;
		bool first=true;
		bool y;
		for(i=0;i<n;i++)
		{	
			y=false;
			for(j=0;j<n;j++)
			{	
				if(read[i][0]==ba[j][0]&&read[i][1]==ba[j][1]&&ba[j][3]==1)
				{	
					ba[j][3]=0;
					y=true;
					break;
				}
			}
			if(y) 
			{	
				if(first) {
					cout<<1;
					first=false;
				}
				else cout<<" "<<1;
			}
			else 
			{	
				if(first)
				{	
					first=false;
					cout<<0;
				}
				else 
				cout<<" "<<0;
			}
		}
		cout<<endl;
	}
	return 0;
}

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

点赞

发表评论

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