01背包代碼java的簡(jiǎn)單介紹
java實(shí)現(xiàn)01背包,代碼如下,有一個(gè)越界異常,已在代碼上標(biāo)注,給看下唄,若不對(duì)給點(diǎn)意見,多謝大俠們.
paks[v-pak[i].cost])
創(chuàng)新互聯(lián)擁有一支富有激情的企業(yè)網(wǎng)站制作團(tuán)隊(duì)，在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)深耕10多年，專業(yè)且經(jīng)驗(yàn)豐富。10多年網(wǎng)站優(yōu)化營(yíng)銷經(jīng)驗(yàn)，我們已為上千余家中小企業(yè)提供了成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作解決方案，按需設(shè)計(jì)網(wǎng)站，設(shè)計(jì)滿意，售后服務(wù)無憂。所有客戶皆提供一年免費(fèi)網(wǎng)站維護(hù)!
這個(gè)地方的問題 ， 你看下那個(gè) v - pak[i].cost 這個(gè)是會(huì)出現(xiàn)負(fù)數(shù)
01背包問題
算法分析
對(duì)于背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，算法設(shè)計(jì)如下：
function Make( i {處理到第i件物品} , j{剩余的空間為j}:integer) :integer;
初始時(shí)i=m , j=背包總?cè)萘?/p>
begin
if i:=0 then
Make:=0;
if j=wi then (背包剩余空間可以放下物品 i )
r1:=Make(i-1,j-wi)+v; (第i件物品放入所能得到的價(jià)值 )
r2:=Make(i-1,j) (第i件物品不放所能得到的價(jià)值 )
Make:=max{r1,r2}
end;
這個(gè)算法的時(shí)間復(fù)雜度是O(2^n)，我們可以做一些簡(jiǎn)單的優(yōu)化。
由于本題中的所有物品的體積均為整數(shù)，經(jīng)過幾次的選擇后背包的剩余空間可能會(huì)相等，在搜索中會(huì)重復(fù)計(jì)算這些結(jié)點(diǎn)，所以，如果我們把搜索過程中計(jì)算過的結(jié)點(diǎn)的值記錄下來，以保證不重復(fù)計(jì)算的話，速度就會(huì)提高很多。這是簡(jiǎn)單?quot;以空間換時(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 件物品中選擇若干件放在所?？臻g為 j 的背包里所能獲得的最大價(jià)值
f[i,j]=max{f[i-1,j-Wi]+Pi (j=Wi), f[i-1,j]}
這個(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件物品放入剩下的容量為v-c的背包中”，此時(shí)能獲得的最大價(jià)值就是f[v-c]再加上通過放入第i件物品獲得的價(jià)值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進(jìn)背包能獲得的最大價(jià)值，也就是f[m,w]
算法設(shè)計(jì)如下：
procedure Make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j=w) and (f[i-1,j-w]+vf[i,j]) then
f[i,j]:=f[i-1,j-w]+v;
end;
writeln(f[m,wt]);
end;
由于是用了一個(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)上好像是矛盾的。
事實(shí)上，由于我們定下的前提是：所有的結(jié)點(diǎn)都沒有重疊。也就是說，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整數(shù)，那末這個(gè)時(shí)候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1
此時(shí)n*w2^n，動(dòng)態(tài)規(guī)劃比搜索還要慢~~|||||||所以，其實(shí)背包的總?cè)萘縒和重疊的結(jié)點(diǎn)的個(gè)數(shù)是有關(guān)的。
考慮能不能不計(jì)算那些多余的結(jié)點(diǎn)……
優(yōu)化時(shí)間復(fù)雜度
以上方法的時(shí)間和空間復(fù)雜度均為O(N*V)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(V)。
先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來二維數(shù)組f[0..V]的所有值。那么，如果只用一個(gè)數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[v]呢？f[v]是由f[v]和f[v-c]兩個(gè)子問題遞推而來，能否保證在推f[v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[v]和f[v-c]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[v-c]保存的是狀態(tài)f[v-c]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c]+w};
其中的f[v]=max{f[v],f[v-c]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[v]=max{f[v],f[v-c]}，因?yàn)楝F(xiàn)在的f[v-c]就相當(dāng)于原來的f[v-c]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[v]由f[v-c]推知，與本題意不符，但它卻是另一個(gè)重要的背包問題P02最簡(jiǎn)捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。
事實(shí)上，使用一維數(shù)組解01背包的程序在后面會(huì)被多次用到，所以這里抽象出一個(gè)處理一件01背包中的物品過程，以后的代碼中直接調(diào)用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個(gè)參數(shù)cost、weight分別表明這件物品的費(fèi)用和價(jià)值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個(gè)過程里的處理與前面給出的偽代碼有所不同。前面的示例程序?qū)懗蓈=V..0是為了在程序中體現(xiàn)每個(gè)狀態(tài)都按照方程求解了，避免不必要的思維復(fù)雜度。而這里既然已經(jīng)抽象成看作黑箱的過程了，就可以加入優(yōu)化。費(fèi)用為cost的物品不會(huì)影響狀態(tài)f[0..cost-1]，這是顯然的。
有了這個(gè)過程以后，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c,w);
初始化的細(xì)節(jié)問題
我們看到的求最優(yōu)解的背包問題題目中，事實(shí)上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時(shí)的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實(shí)現(xiàn)方法是在初始化的時(shí)候有所不同。
如果是第一種問法，要求恰好裝滿背包，那么在初始化時(shí)除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。
如果并沒有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f[0..V]全部設(shè)為0。
為什么呢？可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。
這個(gè)小技巧完全可以推廣到其它類型的背包問題，后面也就不再對(duì)進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解
_'>回溯法解決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）
關(guān)于這個(gè)java語(yǔ)言描述的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;
}
01背包問題變種：從給定的N個(gè)正數(shù)中選取若干個(gè)數(shù)之和最接近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;
java語(yǔ)言，背包問題，從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)，我們可以做一些簡(jiǎn)單的優(yōu)化。
由于本題中的所有物品的體積均為整數(shù)，經(jīng)過幾次的選擇后背包的剩余空間可能會(huì)相等，在搜索中會(huì)重復(fù)計(jì)算這些結(jié)點(diǎn)，所以，如果我們把搜索過程中計(jì)算過的結(jié)點(diǎn)的值記錄下來，以保證不重復(fù)計(jì)算的話，速度就會(huì)提高很多。這是簡(jiǎn)單的“以空間換時(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)上好像是矛盾的。
分享文章：01背包代碼java的簡(jiǎn)單介紹
文章URL：http://m.jiaotiyi.com/article/dociegg.html