_'>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_

因為你把n和c 定義為static ,而且初始化為0,。數(shù)組也為靜態(tài)的,一個類中靜態(tài)的變量在這個類加載的時候就會執(zhí)行，所以當你這類加載的時候，你的數(shù)組static int[] v = new int[n];

成都創(chuàng)新互聯(lián)專注于做網(wǎng)站、網(wǎng)站建設、網(wǎng)頁設計、網(wǎng)站制作、網(wǎng)站開發(fā)。公司秉持“客戶至上,用心服務”的宗旨,從客戶的利益和觀點出發(fā),讓客戶在網(wǎng)絡營銷中找到自己的駐足之地。尊重和關懷每一位客戶，用嚴謹?shù)膽B(tài)度對待客戶，用專業(yè)的服務創(chuàng)造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

static int[] w = new int[n];

就已經(jīng)初始化完畢，而且數(shù)組大小為0。在main方法里動態(tài)改變n的值是改變不了已經(jīng)初始化完畢的數(shù)組的大小的，因為組已經(jīng)加載完畢。

我建議你可以在定義n,c是就為其賦初值。比如（static int n=2 static int c=3）

java語言，背包問題，從Excel表中讀取數(shù)據(jù)

基本概念

問題雛形

01背包題目的雛形是：

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

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

其狀態(tài)轉移方程是：

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

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

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

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]);

問題描述

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

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

算法分析

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

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

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)，我們可以做一些簡單的優(yōu)化。

由于本題中的所有物品的體積均為整數(shù)，經(jīng)過幾次的選擇后背包的剩余空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單的“以空間換時間”。

我們發(fā)現(xiàn)，由于這些計算過程中會出現(xiàn)重疊的結點，符合動態(tài)規(guī)劃中子問題重疊的性質。

同時，可以看出如果通過第N次選擇得到的是一個最優(yōu)解的話，那么第N-1次選擇的結果一定也是一個最優(yōu)解。這符合動態(tài)規(guī)劃中最優(yōu)子問題的性質。

解決方案

考慮用動態(tài)規(guī)劃的方法來解決，這里的：

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

狀態(tài)：在前N件物品中，選取若干件物品放入所?？臻g為W的背包中的所能獲得的最大價值

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

由此可以寫出動態(tài)轉移方程：

我們用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;

}

由于是用了一個二重循環(huán)，這個算法的時間復雜度是O（n*w)。而用搜索的時候，當出現(xiàn)最壞的情況，也就是所有的結點都沒有重疊，那么它的時間復雜度是O（2^n)?？瓷先デ罢咭旌芏?。但是，可以發(fā)現(xiàn)在搜索中計算過的結點在動態(tài)規(guī)劃中也全都要計算，而且這里算得更多（有一些在最后沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。

0-1背包問題java代碼

import?java.io.BufferedInputStream;

import?java.util.Scanner;

public?class?test?{

public?static?int[]?weight?=?new?int[101];

public?static?int[]?value?=?new?int[101];

public?static?void?main(String[]?args)?{

Scanner?cin?=?new?Scanner(new?BufferedInputStream(System.in));

int?n?=?cin.nextInt();

int?W?=?cin.nextInt();

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

weight[i]?=?cin.nextInt();

value[i]?=?cin.nextInt();

}

cin.close();

System.out.println(solve(0,?W,?n));?//?普通遞歸

System.out.println("=========");

System.out.println(solve2(weight,?value,?W));?//?動態(tài)規(guī)劃表

}

public?static?int?solve(int?i,?int?W,?int?n)?{

int?res;

if?(i?==?n)?{

res?=?0;

}?else?if?(W??weight[i])?{

res?=?solve(i?+?1,?W,?n);

}?else?{

res?=?Math.max(solve(i?+?1,?W,?n),?solve(i?+?1,?W?-?weight[i],?n)?+?value[i]);

}

return?res;

}

public?static?int?solve2(int[]?weight,?int[]?value,?int?W)?{

int[][]?dp?=?new?int[weight.length?+?1][W?+?1];

for?(int?i?=?weight.length?-?1;?i?=?0;?--i)?{

for?(int?j?=?W;?j?=?0;?--j)?{

dp[i][j]?=?dp[i?+?1][j];?//?從右下往左上，i+1就是剛剛記憶過的背包裝到i+1重量時的最大價值

if?(j?+?weight[i]?=?W)?{?//?dp[i][j]就是背包已經(jīng)裝了j的重量時，能夠獲得的最大價值

dp[i][j]?=?Math.max(dp[i][j],?value[i]?+?dp[i?+?1][j?+?weight[i]]);

//?當背包重量為j時，要么沿用剛剛裝的，本次不裝，最大價值dp[i][j]，要么就把這個重物裝了，那么此時背包裝的重量為j+weight[i]，

//?用本次的價值value[i]加上背包已經(jīng)裝了j+weight[i]時還能獲得的最大價值，因為是從底下往上，剛剛上一步算過，可以直接用dp[i+1][j+weight[i]]。

//?然后選取本次不裝weight[i]重物時獲得的最大價值以及本次裝weight[i]重物獲得的最大價值兩者之間的最大值

}

}

}

return?dp[0][0];

}

}

關于這個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;

}