快捷導(dǎo)航

C++回溯與分支限界算法分別解決背包問(wèn)題詳解

更新時(shí)間：2022年06月30日 09:37:55 作者：成就一億技術(shù)人

給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？下面我們分別用回溯與分支限界方法解決

算法思想

分支限界法與回溯法的求解目標(biāo)不同。

回溯法的求解目標(biāo)是找出解空間中滿足約束條件的所有解,而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。

由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法對(duì)解空間的搜索方式也不相同。

回溯法以深度優(yōu)先的方式搜索解空間，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間。

回溯法對(duì)解空間做深度優(yōu)先搜索時(shí)，有遞歸回溯和迭代回溯（非遞歸）兩種方法，但一般情況下用遞歸方法實(shí)現(xiàn)回溯法。

常見的兩種分支限界法

　先進(jìn)先出（FIFO）隊(duì)列式:在先進(jìn)先出的分支限界法中，用隊(duì)列作為組織活結(jié)點(diǎn)表的數(shù)據(jù)結(jié)構(gòu)，并按照隊(duì)列先進(jìn)先出的原則選擇結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)。　

優(yōu)先隊(duì)列（PQ）：用優(yōu)先隊(duì)列作為組織活結(jié)點(diǎn)表的數(shù)據(jù)結(jié)構(gòu)。

回溯代碼

#include<stdio.h>
int n,c,bestp;//物品的個(gè)數(shù)，背包的容量，最大價(jià)值
int p[10000],w[10000],x[10000],bestx[10000];//物品的價(jià)值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況
void Backtrack(int i,int cp,int cw)
{ //cw當(dāng)前包內(nèi)物品重量，cp當(dāng)前包內(nèi)物品價(jià)值
    int j;
    if(i>n)//回溯結(jié)束
    {
        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("請(qǐng)輸入背包最大容量:\n");
    scanf("%d",&c);
    printf("請(qǐng)輸入物品個(gè)數(shù):\n");
    scanf("%d",&n);
    printf("請(qǐng)依次輸入物品的重量:\n");
    for(i=1;i<=n;i++) 
        scanf("%d",&w[i]);
    printf("請(qǐng)依次輸入物品的價(jià)值:\n");
    for(i=1;i<=n;i++) 
        scanf("%d",&p[i]);
    Backtrack(1,0,0);
    printf("最大價(jià)值為:\n");
    printf("%d\n",bestp);
    printf("被選中的物品依次是(0表示未選中，1表示選中)\n");
    for(i=1;i<=n;i++) 
        printf("%d ",bestx[i]);
    printf("\n");
    return 0;
}

回溯結(jié)果

分支限界代碼

#include<iostream>
#include<queue>
using namespace std;
const int maxn=99; 
int n,c;
int w[maxn];
int v[maxn];
int bestv=0;
int bestx[maxn];
int total=1;        //解空間中的節(jié)點(diǎn)數(shù)累計(jì)，全局變量 
struct nodetype        //隊(duì)列中的結(jié)點(diǎn)類型
{
    int no;            //結(jié)點(diǎn)編號(hào)，從1開始 
    int i;            //當(dāng)前結(jié)點(diǎn)在搜索空間中的層次 
    int w;            //當(dāng)前結(jié)點(diǎn)的總重量 
    int v;            //當(dāng)前結(jié)點(diǎn)的總價(jià)值 
    int x[maxn];    //當(dāng)前結(jié)點(diǎn)包含的解向量 
    double ub;        //上界 
};
void input()
{
    cout<<"請(qǐng)輸入物品的個(gè)數(shù)："<<endl;
    cin>>n;
    cout<<"請(qǐng)輸入每個(gè)物品的重量及價(jià)值(如5 4):"<<endl;
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<"請(qǐng)輸入背包的容量："<<endl;
    cin>>c;
}
void bound(nodetype &e)        //計(jì)算分支結(jié)點(diǎn)e的上界 
{
    int i=e.i+1;        //考慮結(jié)點(diǎn)e的余下物品
    int sumw=e.w;
    double sumv=e.v;
    while((sumw+w[i]<=c)&&i<=n) 
    {
        sumw+=w[i];
        sumv+=v[i];
        i++;
    }
    if(i<=n)            //余下物品只能部分裝入 
    e.ub=sumv+(c-sumw)*v[i]/w[i];
    else e.ub=sumv; 
} 
void enqueue(nodetype e,queue<nodetype> &qu)
//結(jié)點(diǎn)e進(jìn)隊(duì)qu 
{
    if(e.i==n)                //到達(dá)葉子節(jié)點(diǎn)，不在擴(kuò)展對(duì)應(yīng)一個(gè)解 
    {
        if(e.v>bestv)        //找到更大價(jià)值的解 
        {
            bestv=e.v;
            for(int j=1;j<=n;j++)
            bestx[j]=e.x[j];
        }
    }
    else qu.push(e);        //非葉子結(jié)點(diǎn)進(jìn)隊(duì)
} 
void bfs()
{
    int j;
    nodetype e,e1,e2;
    queue<nodetype> qu;
    e.i=0;
    e.w=0;
    e.v=0;
    e.no=total++;
    for(j=1;j<=n;j++)
    e.x[j]=0;
    bound(e);
    qu.push(e);
    while(!qu.empty())
    {
        e=qu.front();qu.pop();    //出隊(duì)結(jié)點(diǎn)e 
        if(e.w+w[e.i+1]<=c)        //剪枝，檢查左孩子結(jié)點(diǎn) 
        {
            e1.no=total++;        //建立左孩子結(jié)點(diǎn) 
            e1.i=e.i+1;
            e1.w=e.w+w[e1.i];
            e1.v=e.v+v[e1.i];
            for(j=1;j<=n;j++)
            e1.x[j]=e.x[j];
            e1.x[e1.i]=1;
            bound(e1);        //求左孩子的上界 
            enqueue(e1,qu);    //左孩子結(jié)點(diǎn)進(jìn)隊(duì) 
        }
        e2.no=total++;
        e2.i=e.i+1;
        e2.w=e.w;
        e2.v=e.v; 
        for(j=1;j<=n;j++)
            e2.x[j]=e.x[j];
        e2.x[e2.i]=0;
        bound(e2);
        if(e2.ub>bestv)        //若右孩子結(jié)點(diǎn)可行，則進(jìn)隊(duì)，否則被剪枝 
        enqueue(e2,qu);    
    }
} 
void output()
{
    cout<<"最優(yōu)值是:"<<bestv<<endl;
    cout<<"(";
    for(int i=1;i<=n;i++)
        cout<<bestx[i]<<" ";
    cout<<")";
}
int main()
{
    input();
    bfs();
    output();
    return 0;
 }

分支限界結(jié)果