c語言貪心法01背包,貪心法背包問題c語言

本文目錄一覽：

• 1、編程序解決0 1 背包問題？（c語言）
• 2、關於C++ 01背包問題
• 3、c語言0-1背包問題高手進來
• 4、0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）
• 5、0-1背包問題到底能用貪心法解決嗎？
• 6、貪心算法解決特殊0-1背包問題

編程序解決0 1 背包問題？（c語言）

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace beibao

{

class np

{

private int c = 0;//容量

private wp[] w;//物品

private int cp = 0;//當前價值

private int cw = 0;//當前重量

private int bestp = 0;//當前最優值

///動態規劃中/////////////

private int[] head; //輔助數組

private int[,] p; //輔助數組

public np(wp[] w,int c)

{

p = new int[9999, 2];

this.w = w;

this.c = c;

sort();

tanxin();

huisu();

dongtaiguihua();

}

public void sort()

{

wp wupin;

for (int i = 0; i w.Length-1; i++)

{//從小到大冒泡排序

for (int j = 0; j w.Length-i-1; j++)

{

if (w[i].danweizhongliang w[i + 1].danweizhongliang)

{

wupin = w[i];

w[i] = w[i + 1];

w[i + 1] = wupin;

}

}

}

}

public void tanxin()

{

cp = cw = bestp = 0;

for (int i = 0; i w.Length; i++)

{

w[i].State = false;

}

for (int i = 0; i w.Length; i++)

{

if (cw + w[i].Weight c)

continue;

cw += w[i].Weight;

cp += w[i].Price;

w[i].State = true;

}

Console.WriteLine(“貪心算法:裝入價值”+cp.ToString());

Console.WriteLine(“裝入物品號碼:”);

for (int i = 0; i w.Length; i++)

{

if (w[i].State == true) Console.Write(w[i].number.ToString() + “\t”);

} Console.WriteLine();

}

public void huisu()

{

cp = cw = bestp = 0;

for (int i = 0; i w.Length; i++)

{

w[i].State = false;

}

Backtrack(0);

Console.WriteLine(“回溯法:裝入價值” + bestp.ToString());

Console.WriteLine(“裝入物品號碼:”);

for (int i = 0; i w.Length; i++)

{

if (w[i].State == true) Console.Write(w[i].number.ToString() + “\t”);

} Console.WriteLine();

}

private void Backtrack(int i)

{

if (i = w.Length)

{

bestp = cp; return;

}

if (cw + w[i].Weight = c)

{

cw += w[i].Weight;

cp += w[i].Price;

w[i].State = true;

Backtrack(i + 1);

cw -= w[i].Weight;

cp -= w[i].Price;

}

if (Bound(i + 1) bestp)

{

Backtrack(i + 1); w[i].State = false;

}

}

private double Bound(int i)

{

int cleft = c – cw;

double b =(double ) cp;

while (i w.Length w[i].Weight = cleft)

{

cleft -= w[i].Weight;

b += w[i].Price;

i++;

}

if (i w.Length)

{

b += (double)w[i].Price * (double)cleft / (double)w[i].Weight;

}

return b;

}

public void dongtaiguihua()

{

cp = cw = bestp = 0;

for (int i = 0; i w.Length; i++)

{

w[i].State = false;

}

int m= Knapsack(w.Length);

Console.WriteLine(“動態規劃:裝入價值” + m.ToString());

Console.WriteLine(“裝入物品號碼:”);

for (int i = 0; i w.Length; i++)

{

if (w[i].State == true) Console.Write(w[i].number.ToString() + “\t”);

} Console.WriteLine();

}

private int Knapsack(int n)

{

head = new int[n + 2];

head[n + 1] = 0;

p[0, 0] = 0;

p[0, 1] = 0;

int left = 0;

int right = 0;

int next = 1;

head[n] = 1;

for (int i =n-1; i = 0; i–)

{

int k = left;

for (int j = left; j = right; j++)

{

if (p[j, 0] + w[i].Weight c)

break;

int y = p[j, 0] + w[i].Weight;

int m = p[j, 1] + w[i].Price;

while (k = right p[k, 0] y)

{

p[next, 0] = p[k, 0];

p[next++, 1] = p[k++, 1];

}

if (k = right p[k, 0] == y)

{

if (m p[k, 1]) m = p[k, 1];

k++;

}

if (m p[next – 1, 1])

{

p[next, 0] = y;

p[next++, 1] = m;

}

while (k = right p[k, 1] = p[next – 1, 1])

k++;

}

while (k = right)

{

p[next, 0] = p[k, 0];

p[next++, 1] = p[k++, 1];

}

left = right + 1;

right = next – 1;

head[i] = next;

}

Traceback(n);

return p[next – 1, 1];

}

private void Traceback(int n)

{

int j = p[head[0] – 1, 0];

int m = p[head[0] – 1, 1];

for (int i = 0; i n; i++)

{

w[i].State = false;

for (int k = head[i + 1]; k = head[i] – 1; k++)

{

if (p[k, 0] + w[i].Weight == j p[k, 1] + w[i].Price == m)

{

w[i].State = true;

j = p[k, 0];

m = p[k, 1];

break;

}

}

}

}

}

/// summary

/// 物品類

/// /summary

class wp

{

private int w = 0;

private int p = 0;

private int num;

private bool state=false;

public wp(int w,int p,int n)

{

this.w = w;

this.p = p;

num = n;

}

public int Weight

{

get

{

return w;

}

}

public int Price

{

get

{

return p;

}

}

public bool State

{

set

{

state = value;

}

get

{

return state;

}

}

public double danweizhongliang

{

get

{

return (double)p / (double)w;

}

}

public int number

{

get

{

return num;

}

}

}

}

//////////////////////////////////////////////////

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace beibao

{

class Program

{

static void Main(string[] args)

{

np beobap;

int n = 0;

Console.WriteLine(“物品數量”);

n = Convert.ToInt32(Console.ReadLine());

wp[] wupin = new wp[n];

int c = 0;

Console.WriteLine(“背包容積”);

c = Convert.ToInt32(Console.ReadLine());

for (int i = 0; i n; i++)

{//初始化

int w = 0; int p = 0;

Console.WriteLine(“物品” + (i + 1) + “的重量”);

w = Convert.ToInt32(Console.ReadLine());

Console.WriteLine(“物品” + (i + 1) + “的價值”);

p = Convert.ToInt32(Console.ReadLine());

wupin[i] = new wp(w, p, i);

}

beobap = new np(wupin, c);

}

}

}

這是當初我上學的時候做的，應該沒什麼問題，你看看還可以修改修改，有什麼問題可以再問我

關於C++ 01背包問題

1.  摘要

以背包問題為例，介紹了貪心法與動態規劃的關係以及兩個方案在解決背包問題上的比較。貪心法什麼時候能取到最優界並無一般理論，但對於普通背包問題我們有一個完美的結果——貪心法可取到最優解。介紹了其它一些對背包問題的研究或者拓展。

2.  介紹

貪心算法是我們在《算法設計技巧與分析》這門課中所學習到的幾種重要的算法之一，顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是該算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的從局部的最優選擇，尋找到解決問題的次優解的方法。雖然我們希望貪心算法得到的最終結果也是整體最優的，但是在某些情況下，該算法得到的只是問題的最優解的近似。

3.  算法思想:

貪心法的基本思路：

——從問題的某一個初始解出發逐步逼近給定的目標，以儘可能快的地求得更好的解。當達到某算法中的某一步不能再繼續前進時，算法停止。

該算法存在問題：

1. 不能保證求得的最後解是最佳的；

2. 不能用來求最大或最小解問題；

3. 只能求滿足某些約束條件的可行解的範圍。

實現該算法的過程：

在約束                      下最大。

(2) 動態規劃解決方案：是解決0/1背包問題的最優解

(i) 若i=0或j=0,  V[i,j] = 0

(ii)  若jsi, V[i,j] = V[i-1,j]   (僅用最優的方法，選取前i-1項物品裝入體積為j 的背包，因為第i項體積大於j,裝不下這一項，所以背包裏面的i-1項就達到最大值)

(iii) 若i0和j=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一種情況是包中的i-1項已經達到最大值，第二種情況是i-1項佔j-si的體積再加上第i項的總的價值，取這兩種情況的最大值。)

//sj和vj分別為第j項物品的體積和價值，C是總體積限制。

//V[i,j]表示從前i項{u1,u2,…,un}中取出來的裝入體積為j的背包的物品的最大//價值。[13]

（3）貪心算法解決背包問題有幾種策略：

(i) 一種貪婪準則為：從剩餘的物品中，選出可以裝入背包的價值最大的物品，利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 105。當利用價值貪婪準則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優解為[ 0 , 1 , 1 ]，其總價值為3 0。

(ii) 另一種方案是重量貪婪準則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規則對於前面的例子能產生最優解，但在一般情況下則不一定能得到最優解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當利用重量貪婪策略時，獲得的解為x =[1,0], 比最優解[ 0 , 1 ]要差。

(iii) 還有一種貪婪準則，就是我們教材上提到的，認為，每一項計算yi=vi/si,即該項值和大小的比，再按比值的降序來排序，從第一項開始裝背包，然後是第二項，依次類推，儘可能的多放，直到裝滿背包。

有的參考資料也稱為價值密度pi/wi貪婪算法。這種策略也不能保證得到最優解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 時的最優解。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優解，但它是一個直覺上近似的解。

而且這是解決普通背包問題的最優解，因為在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

如圖1，大體上說明了動態規劃解決的0／1背包問題和貪心算法解決的問題之間的區別，

圖1

（4）貪心算法解決背包問題的算法實現：

代碼如下：

 #include iostream.h

            struct goodinfo

            {

             float p; //物品效益

             float w; //物品重量

             float X; //物品該放的數量

             int flag; //物品編號

            };//物品信息結構體

            void Insertionsort(goodinfo goods[],int n)

            {//插入排序，按pi/wi價值收益進行排序，一般教材上按冒泡排序

             int j,i;

             for(j=2;j=n;j++)

             {

                 goods[0]=goods[j];

                 i=j-1;             

                 while (goods[0].pgoods[i].p)

                 {

                   goods[i+1]=goods[i];

                   i–;

                 }

                 goods[i+1]=goods[0];

             }

            }//按物品效益，重量比值做升序排列

            void bag(goodinfo goods[],float M,int n)

            {

             float cu;

             int i,j;

             for(i=1;i=n;i++)

                goods[i].X=0;

             cu=M;  //背包剩餘容量

             for(i=1;in;i++)

             {

               if(goods[i].wcu)//當該物品重量大與剩餘容量跳出

               break;

               goods[i].X=1;

               cu=cu-goods[i].w;//確定背包新的剩餘容量

             }

             if(i=n)

               goods[i].X=cu/goods[i].w;//該物品所要放的量

            /*按物品編號做降序排列*/

             for(j=2;j=n;j++)

             {

                 goods[0]=goods[j];

                 i=j-1;             

                 while (goods[0].flaggoods[i].flag)

                  {

               goods[i+1]=goods[i];

               i–;

              }

              goods[i+1]=goods[0];

             }

            ///////////////////////////////////////////

             cout”最優解為:”endl;

             for(i=1;i=n;i++)

             {

              cout”第”i”件物品要放:”;

              coutgoods[i].Xendl;

             }

            }

            void main()

            {

             cout”|——–運用貪心法解背包問題———|”endl;

             int j,n;    float M;

             goodinfo *goods;//定義一個指針

             while(j)

             {

             cout”請輸入物品的總數量：”;

             cinn;

             goods=new struct goodinfo [n+1];//

             cout”請輸入背包的最大容量：”;

             cinM;

             coutendl;

             int i;

             for(i=1;i=n;i++)

              { goods[i].flag=i;

               cout”請輸入第”i”件物品的重量:”;

               cingoods[i].w;

               cout”請輸入第”i”件物品的效益:”;

               cingoods[i].p;

               goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比

               coutendl;

              }            

             Insertionsort(goods,n);

             bag(goods,M,n);

             cout”press 1 to run agian”endl;

             cout”press 0 to exit”endl;

             cinj;

             }

            }

c語言0-1背包問題高手進來

#include “stdio.h”

#include “time.h”

#define BOXMAX 10

typedef struct BOX

{

int locate[BOXMAX];

float weight[BOXMAX];

float price[BOXMAX];

int n;

}box;

void main()

{

box bx;

int sign=0;

int row,line;

int maxbox;

int tmp;

float maxvalue=0;

int b_n;

float input;

float b_total;

float gotcount=0;

srand(time(NULL));

while(!sign)

{

printf(“input the number of bpx:”);

scanf(“%d”,b_n);

printf(“\nintput the weight of box:”);

scanf(“%f”,b_total);

if(b_n=BOXMAX)

{

sign=1;

}

}

printf(“\ninput the weight:”);

for(row=0;rowb_n;row++)

{

/*

bx.locate[row]=row+1;

bx.weight[row]=rand()%10+1;

bx.price[row]=rand()%10+1;

*/

bx.locate[row]=row+1;

scanf(“%f”,bx.weight[row]);

}

printf(“\ninput the price:”);

for(row=0;rowb_n;row++)

{

scanf(“%f”,bx.price[row]);

}

printf(“\n\n\nwithout order\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.locate[row]);

}

printf(“\nweight:\n”);

printf(“\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.weight[row]);

}

printf(“\nprice:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.price[row]);

}

for(row=0;rowb_n-1;row++)

{

maxvalue=bx.price[row]/bx.weight[row];

maxbox=row;

for(line=row+1;lineb_n;line++)

{

if((bx.price[line]/bx.weight[line])maxvalue)

{

maxvalue=bx.price[line]/bx.weight[line];

maxbox=line;

}

}

if(maxbox!=row)

{

tmp=bx.weight[row];

bx.weight[row]=bx.weight[maxbox];

bx.weight[maxbox]=tmp;

tmp=bx.price[row];

bx.price[row]=bx.price[maxbox];

bx.price[maxbox]=tmp;

tmp=bx.locate[row];

bx.locate[row]=bx.locate[maxbox];

bx.locate[maxbox]=tmp;

}

}

printf(“\n\n\nlist order\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.locate[row]);

}

printf(“\n”);

printf(“\nweight:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.weight[row]);

}

printf(“\nprice:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.price[row]);

}

row=0;

while(b_total=bx.weight[row])

{

b_total=b_total-bx.weight[row];

gotcount+=bx.price[row];

row+=1;;

}

getcount+=(b_total/bx.weight[row])*bx.price[row];

printf(“\n\n%d”,(int)gotcount);

getch();

getch();

}

上面一點注釋都沒有 呵呵 但主要思想可以給你說一下 就是 貪心酸法 選取最高性價比的 填入 箱子；

箱子輸入所有重量 單位價格之後 排序 按照 性價比最高的 一次填入；

0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）

一.動態規劃求解0-1背包問題

/************************************************************************/

/* 0-1背包問題：

/* 給定n種物品和一個背包

/* 物品i的重量為wi，其價值為vi

/* 背包的容量為c

/* 應如何選擇裝入背包的物品，使得裝入背包中的物品

/* 的總價值最大？

/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，

/* 即裝入或不裝入背包。不能將物品i裝入多次，也

/* 不能只裝入部分的物品i。

/*

/* 1. 0-1背包問題的形式化描述：

/* 給定c0, wi0, vi0, 0=i=n，要求找到一個n元的

/* 0-1向量(x1, x2, …, xn), 使得：

/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：

/* (1) sum_{i=1 to n} (wi*xi) = c

/* (2) xi∈{0, 1}, 1=i=n

/*

/* 2. 0-1背包問題的求解

/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於

/* 採用動態規劃方法求解

/*

/* 2.1 最優子結構性質

/* 設(y1,y2,…,yn)是給定0-1背包問題的一個最優解，則必有

/* 結論，(y2,y3,…,yn)是如下子問題的一個最優解：

/* max sum_{i=2 to n} (vi*xi)

/* (1) sum_{i=2 to n} (wi*xi) = c – w1*y1

/* (2) xi∈{0, 1}, 2=i=n

/* 因為如若不然，則該子問題存在一個最優解(z2,z3,…,zn)，

/* 而(y2,y3,…,yn)不是其最優解。那麼有：

/* sum_{i=2 to n} (vi*zi) sum_{i=2 to n} (vi*yi)

/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) = c

/* 進一步有：

/* v1*y1 + sum_{i=2 to n} (vi*zi) sum_{i=1 to n} (vi*yi)

/* w1*y1 + sum_{i=2 to n} (wi*zi) = c

/* 這說明：(y1,z2,z3,…zn)是所給0-1背包問題的更優解，那麼

/* 說明(y1,y2,…,yn)不是問題的最優解，與前提矛盾，所以最優

/* 子結構性質成立。

/*

/* 2.2 子問題重疊性質

/* 設所給0-1背包問題的子問題 P(i,j)為：

/* max sum_{k=i to n} (vk*xk)

/* (1) sum_{k=i to n} (wk*xk) = j

/* (2) xk∈{0, 1}, i=k=n

/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,…,n時的子問題

/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優

/* 子結構性質，可以建立m(i,j)的遞歸式：

/* a. 遞歸初始 m(n,j)

/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的

/* //重量，則直接裝入；否則無法裝入。

/* m(n,j) = vn, j=wn

/* m(n,j) = 0, 0=jwn

/* b. 遞歸式 m(i,j)

/* //背包容量為j、可選物品為i,i+1,…,n

/* //如果背包容量jwi，則根本裝不進物品i，所以有：

/* m(i,j) = m(i+1,j), 0=jwi

/* //如果j=wi，則在不裝物品i和裝入物品i之間做出選擇

/* 不裝物品i的最優值：m(i+1,j)

/* 裝入物品i的最優值：m(i+1, j-wi) + vi

/* 所以：

/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j=wi

/*

/************************************************************************/

#define max(a,b) (((a) (b)) ? (a) : (b))

#define min(a,b) (((a) (b)) ? (a) : (b))

template typename Type

void Knapsack(Type* v, int *w, int c, int n, Type **m)

{

//遞歸初始條件

int jMax = min(w[n] – 1, c);

for (int j=0; j=jMax; j++) {

m[n][j] = 0;

}

for (j=w[n]; j=c; j++) {

m[n][j] = v[n];

}

//i從2到n-1，分別對j=wi和0=jwi即使m(i,j)

for (int i=n-1; i1; i–) {

jMax = min(w[i] – 1, c);

for (int j=0; j=jMax; j++) {

m[i][j] = m[i+1][j];

}

for (j=w[i]; j=c; j++) {

m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);

}

}

m[1][c] = m[2][c];

if (c = w[1]) {

m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);

}

}

template typename Type

void TraceBack(Type **m, int *w, int c, int n, int* x)

{

for (int i=1; in; i++) {

if(m[i][c] == m[i+1][c]) x[i] = 0;

else {

x[i] = 1;

c -= w[i];

}

}

x[n] = (m[n][c])? 1:0;

}

int main(int argc, char* argv[])

{

int n = 5;

int w[6] = {-1, 2, 2, 6, 5, 4};

int v[6] = {-1, 6, 3, 5, 4, 6};

int c = 10;

int **ppm = new int*[n+1];

for (int i=0; in+1; i++) {

ppm[i] = new int[c+1];

}

int x[6];

Knapsackint(v, w, c, n, ppm);

TraceBackint(ppm, w, c, n, x);

return 0;

}

二.貪心算法求解0-1背包問題

1.貪心法的基本思路：

——從問題的某一個初始解出發逐步逼近給定的目標，以儘可能快的地求得更好的解。當達到某算法中的某一步不能再繼續前進時，算法停止。

該算法存在問題：

1).不能保證求得的最後解是最佳的；

2).不能用來求最大或最小解問題；

3).只能求滿足某些約束條件的可行解的範圍。

實現該算法的過程：

從問題的某一初始解出發；

while 能朝給定總目標前進一步 do

求出可行解的一個解元素；

由所有解元素組合成問題的一個可行解；

2.例題分析

1).[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。

要求儘可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

價值 10 40 30 50 35 40 30

分析：

目標函數： ∑pi最大

約束條件是裝入的物品總重量不超過背包容量：∑wi=M( M=150)

（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？

（2）每次挑選所佔空間最小的物品裝入是否能得到最優解？

（3）每次選取單位容量價值最大的物品，成為解本題的策略。

程序代碼:(環境:c++)

#includeiostream.h

#define max 100 //最多物品數

void sort (int n,float a[max],float b[max]) //按價值密度排序

{

int j,h,k;

float t1,t2,t3,c[max];

for(k=1;k=n;k++)

c[k]=a[k]/b[k];

for(h=1;hn;h++)

for(j=1;j=n-h;j++)

if(c[j]c[j+1])

{t1=a[j];a[j]=a[j+1];a[j+1]=t1;

t2=b[j];b[j]=b[j+1];b[j+1]=t2;

t3=c[j];c[j]=c[j+1];c[j+1]=t3;

}

}

void knapsack(int n,float limitw,float v[max],float w[max],int x[max])

{float c1; //c1為背包剩餘可裝載重量

int i;

sort(n,v,w); //物品按價值密度排序

c1=limitw;

for(i=1;i=n;i++)

{

if(w[i]c1)break;

x[i]=1; //x[i]為1時，物品i在解中

c1=c1-w[i];

}

}

void main()

{int n,i,x[max];

float v[max],w[max],totalv=0,totalw=0,limitw;

cout”請輸入n和limitw:”;

cinn limitw;

for(i=1;i=n;i++)

x[i]=0; //物品選擇情況表初始化為0

cout”請依次輸入物品的價值：”endl;

for(i=1;i=n;i++)

cinv[i];

coutendl;

cout”請依次輸入物品的重量：”endl;

for(i=1;i=n;i++)

cinw[i];

coutendl;

knapsack (n,limitw,v,w,x);

cout”the selection is:”;

for(i=1;i=n;i++)

{

coutx[i];

if(x[i]==1)

totalw=totalw+w[i];

}

coutendl;

cout”背包的總重量為：”totalwendl; //背包所裝載總重量

cout”背包的總價值為：”totalvendl; //背包的總價值

}

三.回溯算法求解0-1背包問題

1.0-l背包問題是子集選取問題。

一般情況下，0-1背包問題是NP難題。0-1背包

問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類

似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當

右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘

物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右

子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後

依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是

右子樹中解的上界。

2.解決辦法思路：

為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考

察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。

回溯法是一個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用於解一些組合數較大的問題。

2.算法框架：

a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。

b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。

3.運用回溯法解題通常包含以下三個步驟：

a.針對所給問題，定義問題的解空間；

b.確定易於搜索的解空間結構；

c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；

#includeiostream

using namespace std;

class Knap

{

friend int Knapsack(int p[],int w[],int c,int n );

public:

void print()

{

for(int m=1;m=n;m++)

{

coutbestx[m]” “;

}

coutendl;

};

private:

int Bound(int i);

void Backtrack(int i);

int c;//背包容量

int n; //物品數

int *w;//物品重量數組

int *p;//物品價值數組

int cw;//當前重量

int cp;//當前價值

int bestp;//當前最優值

int *bestx;//當前最優解

int *x;//當前解

};

int Knap::Bound(int i)

{

//計算上界

int cleft=c-cw;//剩餘容量

int b=cp;

//以物品單位重量價值遞減序裝入物品

while(i=nw[i]=cleft)

{

cleft-=w[i];

b+=p[i];

i++;

}

//裝滿背包

if(i=n)

b+=p[i]/w[i]*cleft;

return b;

}

void Knap::Backtrack(int i)

{

if(in)

{

if(bestpcp)

{

for(int j=1;j=n;j++)

bestx[j]=x[j];

bestp=cp;

}

return;

}

if(cw+w[i]=c) //搜索左子樹

{

x[i]=1;

cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i];

}

if(Bound(i+1)bestp)//搜索右子樹

{

x[i]=0;

Backtrack(i+1);

}

}

class Object

{

friend int Knapsack(int p[],int w[],int c,int n);

public:

int operator=(Object a)const

{

return (d=a.d);

}

private:

int ID;

float d;

};

int Knapsack(int p[],int w[],int c,int n)

{

//為Knap::Backtrack初始化

int W=0;

int P=0;

int i=1;

Object *Q=new Object[n];

for(i=1;i=n;i++)

{

Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i];

P+=p[i];

W+=w[i];

}

if(W=c)

return P;//裝入所有物品

//依物品單位重量排序

float f;

for( i=0;in;i++)

for(int j=i;jn;j++)

{

if(Q[i].dQ[j].d)

{

f=Q[i].d;

Q[i].d=Q[j].d;

Q[j].d=f;

}

}

Knap K;

K.p = new int[n+1];

K.w = new int[n+1];

K.x = new int[n+1];

K.bestx = new int[n+1];

K.x[0]=0;

K.bestx[0]=0;

for( i=1;i=n;i++)

{

K.p[i]=p[Q[i-1].ID];

K.w[i]=w[Q[i-1].ID];

}

K.cp=0;

K.cw=0;

K.c=c;

K.n=n;

K.bestp=0;

//回溯搜索

K.Backtrack(1);

K.print();

delete [] Q;

delete [] K.w;

delete [] K.p;

return K.bestp;

}

void main()

{

int *p;

int *w;

int c=0;

int n=0;

int i=0;

char k;

cout”0-1背包問題——回溯法 “endl;

cout” by zbqplayer “endl;

while(k)

{

cout”請輸入背包容量(c)：”endl;

cinc;

cout”請輸入物品的個數(n)：”endl;

cinn;

p=new int[n+1];

w=new int[n+1];

p[0]=0;

w[0]=0;

cout”請輸入物品的價值(p)：”endl;

for(i=1;i=n;i++)

cinp[i];

cout”請輸入物品的重量(w)：”endl;

for(i=1;i=n;i++)

cinw[i];

cout”最優解為(bestx)：”endl;

cout”最優值為(bestp)：”endl;

coutKnapsack(p,w,c,n)endl;

cout”[s] 重新開始”endl;

cout”[q] 退出”endl;

cink;

}

四.分支限界法求解0-1背包問題

1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。

2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。

#include iostream.h

struct good

{

int weight;

int benefit;

int flag;//是否可以裝入標記

};

int number=0;//物品數量

int upbound=0;

int curp=0, curw=0;//當前效益值與重量

int maxweight=0;

good *bag=NULL;

void Init_good()

{

bag=new good [number];

for(int i=0; inumber; i++)

{

cout”請輸入第件”i+1″物品的重量:”;

cinbag[i].weight;

cout”請輸入第件”i+1″物品的效益:”;

cinbag[i].benefit;

bag[i].flag=0;//初始標誌為不裝入背包

coutendl;

}

}

int getbound(int num, int *bound_u)//返回本結點的c限界和u限界

{

for(int w=curw, p=curp; numnumber (w+bag[num].weight)=maxweight; num++)

{

w=w+bag[num].weight;

p=w+bag[num].benefit;

}

*bound_u=p+bag[num].benefit;

return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );

}

void LCbag()

{

int bound_u=0, bound_c=0;//當前結點的c限界和u限界

for(int i=0; inumber; i++)//逐層遍歷解樹決定是否裝入各個物品

{

if( ( bound_c=getbound(i+1, bound_u) )upbound )//遍歷左子樹

upbound=bound_u;//更改已有u限界,不更改標誌

if( getbound(i, bound_u)bound_c )//遍歷右子樹

//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入

{

upbound=bound_u;//更改已有u限界

curp=curp+bag[i].benefit;

curw=curw+bag[i].weight;//從已有重量和效益加上新物品

bag[i].flag=1;//標記為裝入

}

}

}

void Display()

{

cout”可以放入背包的物品的編號為：”;

for(int i=0; inumber; i++)

if(bag[i].flag0)

couti+1″ “;

coutendl;

delete []bag;

}

0-1背包問題到底能用貪心法解決嗎？

0-1背包問題不能用貪心法解決，但是部分背包問題可以用貪心法解決。首先0-1背包是要麼不拿，要拿就得把這類物品全部拿完。網頁鏈接可以參考這個看看

貪心算法解決特殊0-1背包問題

void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]為每個物品的重量，c為背包容量

{

int i;

for(i=1;i=n;i++) x[i]=0;

for(i=1;i=n;i++)

{

if(w[i]c) break;

x[i]=1;

c-=w[i];

}

}