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


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

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

    #include<stdio.h>  
    int n,c,bestp;//物品的個數(shù)，背包的容量，最大價值  
    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("請輸入物品個數(shù):\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;  
    }  

標簽： 搜索

版權申明：本站文章部分自網(wǎng)絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。