關於回溯01背包java的信息

本文目錄一覽：

• 1、0-1背包問題的回溯法中，剪枝用的上界函數問題
• 2、0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）
• 3、關於這個java語言描述的0-1背包問題是否有錯誤？
• 4、01背包問題變種：從給定的N個正數中選取若干個數之和最接近M的JAVA寫法
• 5、關於01背包問題
• 6、java語言，背包問題，從Excel表中讀取數據

0-1背包問題的回溯法中，剪枝用的上界函數問題

不知道你哪裡看的代碼，01背包的分支限界法一般有2種剪枝

1、當去了i後體積超過背包容量，那麼剪去該子樹，體積都超了價值再大也沒用。

2、當前價值+i子樹中所有物品的價值=記錄的最優值，應該就是你說的把。

按單位價值貪心雖然不知道你具體指什麼，我的理解是i的單位價值很低就剪了，這應該是不對的，萬一i後面有個單位價值很高的怎麼辦。

另外，01背包哪有人會用回溯法啊，這是多麼沒有效率的算法啊，雖然有剪枝，但時間複雜度還是指數級的啊，你想想如果有10件物品的話，你的葉節點就有1024個了，如果100件的話，我。。。。。。！！

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;

}

關於這個java語言描述的0-1背包問題是否有錯誤？

有點問題：

public static void knapsack(int[]v,int[]w,int c,int[][]m)

{

int n=v.length-1;

int jMax=Math.min(w[n]-1,c);

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

m[n][j]=0;

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

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

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

{

jMax=Math.min(w[i]-1,c);

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

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

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

m[i][j]=Math.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]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);

}

public static void traceback(int[][]m,int[]w,int c,int[]x)

{

int n=w.length-1;

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]0)?1:0;

}

//int n=w.length-1;

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]0)?1:0;

}

01背包問題變種：從給定的N個正數中選取若干個數之和最接近M的JAVA寫法

BIAS0:= (C-MA(C,2))/MA(C,2)*100;

BIAS1 := (C-MA(C,12))/MA(C,12)*100;

BIAS2 := (C-MA(C,26))/MA(C,26)*100;

BIAS3 := (C-MA(C,48))/MA(C,48)*100;

HXL:=V/CAPITAL*100;

D1:=INDEXC;

D2:=MA(D1,56);

DR2:=D1/D20.94;

E1:=(C-HHV(C,12))/HHV(C,12)*10;

E2:=(C-REF(C,26))/REF(C,26)*10;

關於01背包問題

實在是佩服，精神可嘉，但我還是建議你把dp學會。不會dp的話實在是寸步難行啊！

dp的複雜度為O(n)

窮舉的複雜度為O(2^n)

回溯的時間複雜度介於兩者之間，但還是非常大的。對於大規模的數據肯定會爆。好自為之吧！

java語言，背包問題，從Excel表中讀取數據

基本概念

問題雛形

01背包題目的雛形是：

有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。

其狀態轉移方程是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

對於這方方程其實並不難理解，方程之中，現在需要放置的是第i件物品，這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包，而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。

理解了這個方程後，將方程代入實際題目的應用之中，可得

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

for (j = v; j = c[i]; j–)//在這裡，背包放入物品後，容量不斷的減少，直到再也放不進了

f[i][j] = max(f[i – 1][j], f[i – 1][j – c[i]] + w[i]);

問題描述

求出獲得最大價值的方案。

注意：在本題中，所有的體積值均為整數。

算法分析

對於背包問題，通常的處理方法是搜索。

用遞歸來完成搜索，算法設計如下：

int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量

{

if (i == 0) return 0;

if (j = c[i])//(背包剩餘空間可以放下物品 i )

{

int r1 = make(i – 1, j – w[i]);//第i件物品放入所能得到的價值

int r2 = make(i – 1, j);//第i件物品不放所能得到的價值

return min(r1, r2);

}

return make(i – 1, j);//放不下物品 i

}

這個算法的時間複雜度是O(n^2)，我們可以做一些簡單的優化。

由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重複計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重複計算的話，速度就會提高很多。這是簡單的「以空間換時間」。

我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。

同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。

解決方案

考慮用動態規劃的方法來解決，這裡的：

階段：在前N件物品中，選取若干件物品放入背包中

狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值

決策：第N件物品放或者不放

由此可以寫出動態轉移方程：

我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值

f[i][j] = max(f[i – 1][j – W[i]] + P[i], f[i – 1][j]);//j = W[ i ]

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入已用的容量為c的背包中」，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。

這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]

算法設計如下：

int main()

{

cin n v;

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

cin c[i];//價值

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

cin w[i];//體積

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

f[i][0] = 0;

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

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

if (j = w[i])//背包容量夠大

f[i][j] = max(f[i – 1][j – w[i]] + c[i], f[i – 1][j]);

else//背包容量不足

f[i][j] = f[i – 1][j];

cout f[n][v] endl;

return 0;

}

由於是用了一個二重循環，這個算法的時間複雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間複雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這裡算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。