經典算法9：回溯法之0--1背包問題

1.題目分析：
考慮到每種物品只有2種選擇，即裝入背包或不裝入背包，并且物品數和背包容量已給定，要計算裝入背包物品的最大價值和最優裝入方案，可用回溯法搜索子集樹的算法進行求解。


2.算法設計：
a. 物品有n種，背包容量為C，分別用p[i]和w[i]存儲第i種物品的價值和重量，用
x[i]標記第i種物品是否裝入背包，用bestx[i]存儲第i種物品的最優裝載方案；
b. 用遞歸函數Backtrack (i,cp,cw)來實現回溯法搜索子集樹（形式參數i表示遞歸深
度，n用來控制遞歸深度，形式參數cp和cw表示當前總價值和總重量，bestp表示當前
最優總價值）：
① 若i >n，則算法搜索到一個葉結點，判斷當前總價值是否最優：
1> 若cp>bestp，更新當前最優總價值為當前總價值（即bestp=cp），更新
裝載方案（即bestx[i]=xi）；
② 采用for循環對物品i裝與不裝兩種情況進行討論（0≤j≤1）：
1> x[i]=j；
2> 若總重量不大于背包容量（即cw+x[i]w[i]<=c），則更新當前總價 br=""> 值和總重量（即cw+=w[i]x[i],cp+=p[i]x[i]）, 對物品i+1調用遞歸函
數Backtrack(i+1,cp,cw) 繼續進行裝載；
3> 函數Backtrack(i+1,cp,cw)調用結束后則返回當前總價值和總重量
（即 cw-=w[i]x[i],cp-=p[i]*x[i]）；
4> 當j>1時，for循環結束；
③ 當i=1時，若已測試完所有裝載方案，外層調用就全部結束；

c. 主函數調用一次backtrack(1,0,0)即可完成整個回溯搜索過程，最終得到的bestp和bestx[i]即為所求最大總價值和最優裝載方案。

    #include<stdio.h>

    int n,c,bestp;//物品的個數，背包的容量，最大價值

    int p[10000],w[10000],x[10000],bestx[10000];//物品的價值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況


void Backtrack(int i,int cp,int cw)  
{ //cw當前包內物品重量，cp當前包內物品價值  
    int j;  
    if(i>n)//回溯結束  
    {  
        if(cp>bestp)  
        {  
            bestp=cp;  
            for(i=0;i<=n;i++) bestx[i]=x[i];  
        }  
    }  
    else   
        for(j=0;j<=1;j++)    
        {  
            x[i]=j;  
            if(cw+x[i]*w[i]<=c)    
            {  
                cw+=w[i]*x[i];  
                cp+=p[i]*x[i];  
                Backtrack(i+1,cp,cw);  
                cw-=w[i]*x[i];  
                cp-=p[i]*x[i];  
            }  
        }  
}  

int main()  
{  
    int i;  
    bestp=0;   
    printf("請輸入背包最大容量:\n");  
    scanf("%d",&c);  
    printf("請輸入物品個數:\n");  
    scanf("%d",&n);  
    printf("請依次輸入物品的重量:\n");  
    for(i=1;i<=n;i++)   
        scanf("%d",&w[i]);  
    printf("請依次輸入物品的價值:\n");  
    for(i=1;i<=n;i++)   
        scanf("%d",&p[i]);  
    Backtrack(1,0,0);  
    printf("最大價值為:\n");  
    printf("%d\n",bestp);  
    printf("被選中的物品依次是(0表示未選中，1表示選中)\n");  
    for(i=1;i<=n;i++)   
        printf("%d ",bestx[i]);  
    printf("\n");  
    return 0;  
}  </pre>