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

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

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

---

0-1背包問題描述：

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

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

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

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

---

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

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

在當(dāng)前的可擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新的結(jié)點(diǎn)，這個(gè)新結(jié)點(diǎn)成為當(dāng)前的活結(jié)點(diǎn)，并成為擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的可擴(kuò)展結(jié)點(diǎn)處不能向縱深方向移動(dòng)（結(jié)點(diǎn)不包含問題解，或者到達(dá)葉子結(jié)點(diǎn)），則當(dāng)前擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)。此時(shí)，應(yīng)回溯至最近的一個(gè)活動(dòng)結(jié)點(diǎn)處，并使這個(gè)活動(dòng)結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或者解空間中已無活動(dòng)結(jié)點(diǎn)為止。

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

cw?? :當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的載重量 ;

?r??? :當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的剩余集裝箱重量;

回溯法解題步驟：

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

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

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

剪枝函數(shù)：

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

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

遞歸回溯流程圖：

---

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

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

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

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

---

源代碼：

#includeusing namespace std;
class Knap{
    friend int Knapsack(int*,int*,int,int,Knap&);
public:
    int c;      //背包容量
    int n;      //物品個(gè)數(shù)
    int* w;     //重量信息
    int* p;     //價(jià)值信息
    int cw;     //當(dāng)前重量
    int cp;     //當(dāng)前價(jià)值
    int bestp;  //當(dāng)前最優(yōu)價(jià)值
    int *x,     //當(dāng)前解
        *bestx; //當(dāng)前最優(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海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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