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\n",s);
    for(i=0;i<n;i++)
    {
        if(i==0)
        {
            printf("%d",x[i]);
        }
        else
            printf(" %d",x[i]);
    }
    printf("\n");
}