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

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

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

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

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

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

基本概念

問題雛形

01背包題目的雛形是：

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

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

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

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

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

理解了這個(gè)方程后，將方程代入實(shí)際題目的應(yīng)用之中，可得

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

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

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

問題描述

求出獲得最大價(jià)值的方案。

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

算法分析

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

用遞歸來完成搜索，算法設(shè)計(jì)如下：

int make(int i, int j)//處理到第i件物品,剩余的空間為j 初始時(shí)i=m , j=背包總?cè)萘?/p>

{

if (i == 0) return 0;

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

{

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

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

return min(r1, r2);

}

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

}

這個(gè)算法的時(shí)間復(fù)雜度是O(n^2)，我們可以做一些簡單的優(yōu)化。

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

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

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

解決方案

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

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

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

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

由此可以寫出動(dòng)態(tài)轉(zhuǎn)移方程：

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

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

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

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

算法設(shè)計(jì)如下：

int main()

{

cin n v;

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

cin c[i];//價(jià)值

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;

}

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

關(guān)于這個(gè)java語言描述的0-1背包問題是否有錯(cuò)誤？

有點(diǎn)問題：

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;

}