01背包问题南邮NOJ 1308

背包问题

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 79 测试通过 : 30

题目描述

试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解0-1背包问题。

0-1 背包问题描述如下：给定n 种物品和一个背包。物品i 的重量是 wi ，其价值为 v i，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有2 种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分的物品i。

0-1 背包问题形式化描述：给定C＞0， Wi ＞0， Vi ＞0，1≤i≤n，要求n 元0-1向量( x1 ，x2 ，…， xn )，xi∈｛0，1｝，1≤i≤n，使得达到最大

输入

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

输出

计算出装入背包物品的最大价值和最优装入方案。

样例输入

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

样例输出

15
1 1 0 0 1

提示

典型的01背包问题，实现代码如下：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a,int b)
{
   if(a>=b)
       return a;
   else return b;
}

int KnapSack(int n,int w[],int v[],int x[],int C)
{
    int i,j;
    for(i=0;i<=n;i++)
        V[i][0]=0;
    for(j=0;j<=C;j++)
        V[0][j]=0;
    for(i=0;i<=n-1;i++)
        for(j=0;j<=C;j++)
            if(j<w[i])
                V[i][j]=V[i-1][j];
            else
                V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
            j=C;
            for(i=n-1;i>=0;i--)
            {
                if(V[i][j]>V[i-1][j])
                {
                x[i]=1;
                j=j-w[i];
                }
            else
                x[i]=0;
            }
        return V[n-1][C];

}

int main()
{
    int s;//获得的最大价值
    int w[15];//物品的重量
    int v[15];//物品的价值
    int x[15];//物品的选取状态
    int n,i;
    int C;//背包最大容量
    int sum=0;
    n=5;
    scanf("%d%d",&n,&C);
     for(i=0;i<n;i++)
    {  scanf("%d",&v[i]);
          sum+=v[i];
    }
    for(i=0;i<n;i++)
        scanf("%d",&w[i]);
    s=KnapSack(n,w,v,x,C);
    printf("%d
",s);
    for(i=0;i<n;i++)
    {
        if(i==0)
        {
            printf("%d",x[i]);
        }
        else
            printf(" %d",x[i]);
    }
    printf("
");
}

01背包问题 南邮NOJ 1308

背包问题

01背包问题南邮NOJ 1308