回溯法解01背包問題（最通俗易懂，附C++代碼）-創(chuàng)新互聯(lián)

問題描述：

01背包問題是算法中的經(jīng)典問題，問題描述如下：
對(duì)于給定的N個(gè)物品，第i個(gè)物品的重量為Wi，價(jià)值為Vi，對(duì)于一個(gè)最多能裝重量C的背包，應(yīng)該如何選擇放入包中的物品，使得包中物品的總價(jià)值大？

創(chuàng)新互聯(lián)專注于汨羅企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開發(fā),商城開發(fā)。汨羅網(wǎng)站建設(shè)公司,為汨羅等地區(qū)提供建站服務(wù)。全流程專業(yè)公司，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)回溯法簡(jiǎn)介：

回溯法的本質(zhì)其實(shí)就是一種蠻力法，只是通過一定的方法可以使得蠻力法中的一些基本情況可以提前排除從而提高蠻力算法效率，回溯可以理解為排除這些不滿足條件的基本情況的過程。

回溯法求解0-1背包問題的過程：

由于直接描述過程比較抽象，因此直接上例題
例題：假設(shè)N=3（有三件物品），三個(gè)物品的重量為{20，15，10}，三個(gè)物品的價(jià)值為{20，30，25}，對(duì)于一個(gè)大承重為25的背包，求包中物品的組合大的價(jià)值是多少？
題目的參考思路圖如下，建議圖文對(duì)照：（參考書為王紅梅老師的《算法設(shè)計(jì)與分析》）

對(duì)三件物品分別進(jìn)行編號(hào)1，2，3，初始情況背包是空的
1.首先我們把1號(hào)物品放進(jìn)背包里，此時(shí)背包里只有一件物品，總重量為0+20=20，沒有超過承重25，因此可以將1號(hào)物品成功放入背包內(nèi)；
2.接下來嘗試把2號(hào)物品放入背包內(nèi)，但是發(fā)現(xiàn)包中1號(hào)物品和2號(hào)物品的重量和為20+15=35，超過了承重25，因此不能把2號(hào)物品放入背包內(nèi)；
3.接著考慮3號(hào)物品，此時(shí)包中只有1號(hào)物品。發(fā)現(xiàn)1號(hào)物品和3號(hào)物品的重量和為20+10=30，超過了承重25，因此3號(hào)物品也不能放入背包內(nèi)；
4.由于只有3件物品，并且對(duì)于每一種物品我們都考慮過是否將其放入背包內(nèi)，也就是找到了一種基本情況。找到一個(gè)基本情況后，我們就可以看看包里的物品的總價(jià)值了。這里包里只有一個(gè)1號(hào)物品，因此總價(jià)值為20；
5.重點(diǎn)來了！回溯過程：每次找出一種滿足條件的基本情況就進(jìn)行一次回溯，找到最后放入包中的物品并將其取出，接著考慮是否放入編號(hào)在這個(gè)物品之后的第一個(gè)物品。這里我們就把1號(hào)物品取出，接下來考慮是否放入2號(hào)物品；
6.取出1號(hào)物品后背包是空的，此時(shí)如果放入2號(hào)物品，背包總重量為15，沒有超過背包承重，因此把2號(hào)物品放入背包內(nèi)；
7.類似地，考慮將3號(hào)物品放入背包內(nèi)。由于2號(hào)物品和3號(hào)物品的重量和為15+10=25，沒有超過承重25，因此將其放入背包內(nèi)；
8.由于考慮完了3號(hào)物品，因此又找到了一個(gè)基本情況，記下此時(shí)包里物品的總價(jià)值，為30+25=55。由于55高于上一種基本情況的總價(jià)值，因此將最優(yōu)解更新為55；
9.進(jìn)行一次回溯，取出背包中最后放入的物品，也就是3號(hào)物品，但是注意：當(dāng)最后放入背包中的物品恰好是編號(hào)大的物品時(shí)，需要額外進(jìn)行一次回溯。為什么呢？因?yàn)榫幪?hào)大的物品之后已經(jīng)沒有編號(hào)更大的物品了，因此沒有可以考慮的下一種情況，只能在上一個(gè)層面上在進(jìn)行一次回溯才能產(chǎn)生可能的最優(yōu)解。（此處不必考慮只放入2號(hào)物品的情況，因?yàn)橐欢ú皇亲顑?yōu)解，原因可以自己思考一下） 這里再回溯一次，也就是將倒數(shù)第二個(gè)放入包中的物品取出來，這里就取出2號(hào)物品。先后取出3號(hào)物品和2號(hào)物品之后包應(yīng)該處于空的狀態(tài)。
10.上一步中取出了2號(hào)物品，因此這一步直接考慮能否放入3號(hào)物品，簡(jiǎn)單的判斷后即可得出可以放入，并且同上理也可以得出這是一種基本情況，但是由于包中只有3號(hào)物品，總價(jià)值為25，沒有超過當(dāng)前的最優(yōu)解55，因此將該情況忽略。
11.最后一次回溯，取出包中的3號(hào)元素。由于此時(shí)包已經(jīng)空了，并且最后一次取出的是編號(hào)大的元素，那么說明算法已經(jīng)完成了所有情況的遍歷，算法終止，55是最優(yōu)解。

程序代碼：

#include#include//由于問題中的包是需要進(jìn)行后進(jìn)先出的操作，因此考慮到使用棧這種數(shù)據(jù)結(jié)構(gòu)（后進(jìn)先出）
using namespace std;

int maxValue(int w[], int v[], const unsigned& length, const unsigned& capacity)
{stackBag;//首先構(gòu)造出一個(gè)空的背包
    int max = 0;//不同裝入情況中背包中物品大的價(jià)值
    int weight = 0;//當(dāng)前背包中物品的總重量
    int value = 0;//當(dāng)前背包中物品的總價(jià)值
    int i;

    for (i = 0; ; i++)
    {if (weight + w[i]<= capacity)//第一種情況：背包裝入該物品后不會(huì)超重
        {Bag.push(i);//將該物品裝入背包中
            weight += w[i];//裝入物品后背包重量增加
            value += v[i];//裝入物品后背包中物品的價(jià)值增加
        }
        else//第二種情況：裝入該物品后背包超重，則不能將該物品裝入包中，相當(dāng)于什么也不做
        {//此處用else語句只是方便理解這是另外一種情況，可以省略
        }

        //當(dāng)從第一個(gè)物品考慮到了最后一個(gè)物品時(shí)，就確定了一個(gè)可以滿足條件的裝包方法（一個(gè)方法就是確定了一個(gè)規(guī)定每一個(gè)物品是否裝進(jìn)包里的策略）
        if (i == length - 1)
        {//接下來將本次裝包物品價(jià)值與當(dāng)前最高的裝包物品價(jià)值進(jìn)行比較，保留較大的一個(gè)
            if (max< value)
            {max = value;
            }
            //此時(shí)取出最后裝進(jìn)包里的一件物品并對(duì)其下一件物品進(jìn)行考慮（這就是算法的重點(diǎn)：回溯的過程?。?            {i = Bag.top();//取出上一件裝入的東西（這就是回溯的過程）
                Bag.pop();
                weight -= w[i];//取出東西后背包重量減輕
                value -= v[i];//取出物品后背包總價(jià)值也會(huì)降低
                if (i == length - 1)//特殊情況：如果最后裝進(jìn)包里的物品本來在就是編號(hào)大的物品，那么它后面就沒有其他物品了，循環(huán)必定終止
                {if (Bag.empty())break;//當(dāng)所有物品都被從包中拿出來后，這是說明已經(jīng)遍歷完所有情況，查找結(jié)束（相當(dāng)于解空間樹中最右邊的子樹已經(jīng)走完了）
                    i = Bag.top();//取出上一件裝入的東西（這就是回溯的過程）
                    Bag.pop();
                    weight -= w[i];//取出東西后背包重量減輕
                    value -= v[i];//取出物品后背包總價(jià)值也會(huì)降低
                }
            }
        }
    }
    return max;
}

int main(void)
{unsigned num, capacity;
    cout<< "請(qǐng)輸入物品的個(gè)數(shù)：";
    cin >>num;
    int* weights = new int[num];
    int* values = new int[num];
    cout<< "請(qǐng)輸入每件物品的重量：";
    for (unsigned i = 0; i< num; i++)
    {cin>>weights[i];
    }
    cout<< "請(qǐng)輸入每件物品的價(jià)值：";
    for (unsigned i = 0; i< num; i++)
    {cin >>values[i];
    }
    cout<< "請(qǐng)輸入包的大承重：";
    cin >>capacity;
    cout<< "該問題的最優(yōu)解為："<< maxValue(weights, values, num, capacity);
    return 0;
}

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

分享題目：回溯法解01背包問題（最通俗易懂，附C++代碼）-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://muchs.cn/article34/dhshse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、企業(yè)建站、App設(shè)計(jì)、云服務(wù)器、軟件開發(fā)、網(wǎng)站導(dǎo)航

廣告

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