java背包演算法

⑴ 關於這個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;i>1;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;i<n;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;i<n;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;
}

⑵ java演算法背包溢出最小值

java演算法背包溢出最小值最小值-1,即最小值+(-1),即1-0000加1-1111,變成0-1111。

最大值＋1，即0-1111加0-0001，變成1-0000，即最小值最小值－1，即最小值＋（－1)，即1-0000加1-1111，變成0-1111，即最大值正數區間和負數區間形成了循環，正數區間最大值＋1，就進入了負數區間，負數區間最大值＋1，就進入了正數區間。

基本信息

數據結構與演算法課程是電子科技大學於2018年02月26日首次在中國大學MOOC開設的慕課課程、國家精品在線開放課程。該課程授課教師為林劼、戴波、劉震、周益民。據2021年3月中國大學MOOC官網顯示，該課程已開課7次。

數據結構與演算法課程共6個模塊，包括緒論、線性表、查找、排序、遞歸與分治、樹與二叉樹、圖論與貪心演算法、動態規劃等內容。

數據結構與演算法課程是計算機科學與技術的學科基礎課程，也是是計算機圖形學、計算機網路、編譯原理、計算機操作系統等後續課程的基礎理論之一，其應用范圍也早已擴展到圖像處理與模式識別、海量數據挖掘、科學數據處理、復雜網路分析等許多計算機前沿領域。

⑶ 0-1背包問題java代碼

importjava.io.BufferedInputStream;
importjava.util.Scanner;

publicclasstest{
publicstaticint[]weight=newint[101];
publicstaticint[]value=newint[101];

publicstaticvoidmain(String[]args){
Scannercin=newScanner(newBufferedInputStream(System.in));
intn=cin.nextInt();
intW=cin.nextInt();
for(inti=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));//動態規劃表
}

publicstaticintsolve(inti,intW,intn){
intres;
if(i==n){
res=0;
}elseif(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]);
}
returnres;
}

publicstaticintsolve2(int[]weight,int[]value,intW){
int[][]dp=newint[weight.length+1][W+1];
for(inti=weight.length-1;i>=0;--i){
for(intj=W;j>=0;--j){
dp[i][j]=dp[i+1][j];//從右下往左上，i+1就是剛剛記憶過的背包裝到i+1重量時的最大價值
if(j+weight[i]<=W){//dp[i][j]就是背包已經裝了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+weight[i]時還能獲得的最大價值，因為是從底下往上，剛剛上一步算過，可以直接用dp[i+1][j+weight[i]]。
//然後選取本次不裝weight[i]重物時獲得的最大價值以及本次裝weight[i]重物獲得的最大價值兩者之間的最大值
}
}
}
returndp[0][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/D2<0.94;
E1:=(C-HHV(C,12))/HHV(C,12)*10;
E2:=(C-REF(C,26))/REF(C,26)*10;

⑸ 背包問題演算法java實現

任何語言都是一樣的，貪心演算法，先按價值除重量排序，一個一個的加到背包里，當超過背包允許的重量後，去掉最後加進去一個，跳過這一個以後再加後面的，如果還是超重，再跳過這個，一直到價值最大化位置。

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

因為你把n和c 定義為static ,而且初始化為0,。數組也為靜態的,一個類中靜態的變數在這個類載入的時候就會執行，所以當你這類載入的時候，你的數組static int[] v = new int[n];
static int[] w = new int[n];
就已經初始化完畢，而且數組大小為0。在main方法里動態改變n的值是改變不了已經初始化完畢的數組的大小的，因為組已經載入完畢。

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

⑺ java實現01背包,一下為項目源碼,報了一個越界異常,哪位大俠給看看.

把第二個循環中的V++修改為V--

for(int i=0;i<4;i++)
{
for(int v=19;v>=0;v--)
{
//max(paks[v],paks[v-pak[i].cost])
if(leave>pak[i].cost&&paks[v]<paks[v-pak[i].cost])
{
paks[v]=pak[i].worth;
total+=pak[i].worth;
leave-=pak[i].cost;
}
}
}

⑻ 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)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這里算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。

⑼ JAVA背包問題，對於我十萬火急！！！！！！求救！！！！求救！！！！

public class Beibao {

/**
* @param args
*/
static int lenth = 5;
static int T = 10;
static int w[]= {2,4,6,8,10};
static int already = 0;
static int a[]= {0,0,0,0,0};
public static void go(int i)
{
if(already == T)
{
for(int j = 0;j< lenth;j++)
{
System.out.print(a[j]+" ");
}
System.out.println();
}
else
{
for(int m = i;m < lenth;m++)
{
if(a[m] == 0 && already + w[m] <= T)
{
a[m] = 1;
already += w[m];
go(m+1);
a[m] = 0;
already -= w[m];
}
}
}
}
public static void main(String[] args)
{
// TODO Auto-generated method stub
go(0);
}

}