編譯環(huán)境：Dev-C++

10年積累的成都網(wǎng)站制作、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先做網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有宜賓免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

遞歸回溯方法求解0-1背包問題的具體算法實現(xiàn)

---

0-1背包問題描述：

我們有n種物品，物品j的重量為wj，價格為pj。我們假定所有物品的重量和價格都是非負的。背包所能承受的大重量為c。如果限定每種物品只能選擇0個或1個，則問題稱為0-1背包問題。計算出背包能承受的大價值量。

0-1背包問題形式化描述：

給定c＞0，wi＞0，vi＞0，1≤i≤n，求n元0-1向量(x1, x2, …, xn)，使得

在本次試驗中，使用到的實例為：n=7，c=150，w={35,30,60,50,40,10,25}，p={10,40,30,50,35,40,30}.??

---

算法設(shè)計實現(xiàn)描述：

回溯法在包含問題的所有解的解空間樹中按照深度優(yōu)先的策略，確定了解空間的組織結(jié)構(gòu)后，回溯法從開始節(jié)點出發(fā)，以深度優(yōu)先方式搜索整個解空間，這個開始節(jié)點成為活節(jié)點，同時成為當前的擴展結(jié)點。

在當前的可擴展結(jié)點處，搜索向縱深方向移至一個新的結(jié)點，這個新結(jié)點成為當前的活結(jié)點，并成為擴展結(jié)點。如果在當前的可擴展結(jié)點處不能向縱深方向移動（結(jié)點不包含問題解，或者到達葉子結(jié)點），則當前擴展結(jié)點變成死結(jié)點。此時，應回溯至最近的一個活動結(jié)點處，并使這個活動結(jié)點成為當前的擴展結(jié)點?；厮莘ㄒ赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或者解空間中已無活動結(jié)點為止。

不妨設(shè)? bestw :當前最優(yōu)載重量；

cw?? :當前擴展結(jié)點Z的載重量 ;

?r??? :當前擴展結(jié)點Z的剩余集裝箱重量;

回溯法解題步驟：

1、針對所給問題，定義問題的解空間；

2、確定易于搜索的解空間結(jié)構(gòu)；

3、以深度優(yōu)先搜索的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索

剪枝函數(shù)：

1、搜索左子樹時：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的左子樹（約束函數(shù)cw+wi >C時，剪掉左子樹）

2、搜索右子樹時：用限界函數(shù)剪去得不到最優(yōu)解的右子樹（限(上)界函數(shù)cp+r

遞歸回溯流程圖：

---

調(diào)試過程及結(jié)果

程序執(zhí)行的結(jié)果:

0-1背包問題回溯算法的復雜性分析：

在本算法中，計算上界需要O(n)時間，在最壞情況下有O(2-n) 個右兒子結(jié)點需要計算上界。所以，解0-1背包問題的回溯算法Backtrack所需要的計算時間為O(n2-n)。

---

源代碼：

#includeusing namespace std;
class Knap{
    friend int Knapsack(int*,int*,int,int,Knap&);
public:
    int c;      //背包容量
    int n;      //物品個數(shù)
    int* w;     //重量信息
    int* p;     //價值信息
    int cw;     //當前重量
    int cp;     //當前價值
    int bestp;  //當前最優(yōu)價值
    int *x,     //當前解
        *bestx; //當前最優(yōu)解
    int Bound(int i);            //限界函數(shù)
    void Backtrack(int i);       //遞歸深度優(yōu)先遍歷
};
int Knap::Bound(int i){
    int cleft = c - cw;
    int b = cp;
    while(i<=n&&w[i]<=cleft){
        b += p[i];
        cleft -= w[i];
        i++;
    }
    if(i<=n) b += cleft*(p[i]/w[i]);
    return b;
}
void Knap::Backtrack(int i){
    if(i>n){
        bestp = cp;
        for(int i=1;i<=n;i++){
            bestx[i] = x[i];
        }
        for(int i=1;i<=n;i++){
            cout<bestp)//Bound(i+1)代表第i層右子樹的限界函數(shù)
        {
            x[i] = 0;
            Backtrack(i+1);  //繼續(xù)深度優(yōu)先搜索
        }

    }
}
class Object{               //物品類
    friend int Knapsack(int*,int*,int,int,Knap&);
    friend bool cmp(Object,Object);
private:
    int id;
    double aver;
};
bool cmp(Object a,Object b){
    return a.aver>b.aver;
}
int Knapsack(int* w,int* p,int c,int n,Knap& K){
    int W = 0;
    int P = 0;
    Object* Q = new Object[n];
    for(int i=1;i<=n;i++){
        Q[i-1].id = i;
        Q[i-1].aver = 1.0*p[i]/w[i];
        P += p[i];
        W += w[i];
}
    if(W>n>>c;
    w = new int[n+1];
    p = new int[n+1];
    cout<<"input weight of objects"<>w[i];
    }
    cout<<"input value of objects"<>p[i];
    }
}
void Print(int bestp,int n,int*& x){
    cout<<"max value is"<

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：0-1背包問題的遞歸回溯算法實現(xiàn)（C++）-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://www.rwnh.cn/article8/dgseip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標簽優(yōu)化、建站公司、商城網(wǎng)站、關(guān)鍵詞優(yōu)化、域名注冊、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)