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

❸ 回溯法解決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版的背包問題

因為 要求找出所有滿足上述條件的解
所以 全排列組合 來一遍。

❺ 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];
}
}

❻ 背包問題，頭搞大了！網上的代碼

我給你注釋了下，希望你能理解到。

import java.util.Scanner;
public class Backpack{
static float[] weight=new float[100];
static boolean[] flag = new boolean[100];
static boolean fl=false;
static int nn;
public static int Knap(float sum,int n) {

int i;
if (sum==0) { 我輸入總體積為0時，不管物品和物品體積輸什麼，什麼都
for(i=0;i<nn;i++){ 不提示程序就結束了，沒搞懂這段代碼的含義
//你這里直接結束的原因在於你的sum為0，但是你的flag數組裡面全部是false, 凡是定義boolean類型的，java默認為false,
//所以這里的for循環當sum在你第一次sum=0的時候是永遠不會執行的，所以總體積為0的時候就直接跳入System.out.println();返回1，程序返回1正常結束。但是當你開始處理了背包的時候隨著flag數組裡面的值變化（不超過n個物體的下標），這里循環開始慢慢執行的。
if(flag[i]) {
System.out.print("選擇");
System.out.println(weight[i]);
}
}
System.out.println();
fl=true;
return 1;
}
else if (sum<0||(sum>0&&n<0))
return 0;

//即就是拿了最後輸入的那個背包的重量，凡是已經拿取得背包，將對應的flag數組元素標記為true
flag[n]=true; 為什麼這里flag[]變為true?
//減去最後輸入的背包重量，用剩下的n-1個來完成遞歸調用，一直到sum ==0,或者sum < 0 || sum >0 ＆＆n ＜0為止
i=Knap(sum-weight[n],n-1); 這個是什麼含義？
//如果不能滿足上面的條件，也就是說用第n個背包作為第一個結果算組合失敗，所以拋棄最後一個背包（第n個）
flag[n]=false; 為什麼又變成false了？
//將重量重置為起始重量，從倒數第二個背包開始重新遞歸計算
i=Knap(sum,n-1); 這個又是什麼意思？

if(fl)
return 1;
return 0;

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

float sum;
System.out.println("背包總體積:");
Scanner s = new Scanner(System.in);
sum = s.nextFloat();
System.out.println("物品件數:");
nn = s.nextInt();
System.out.println("輸入物品的體積:");
for (int i=0; i<nn; i++)
weight[i] = s.nextFloat();

if (Knap(sum,nn-1)==0)
System.out.println("無解");
}
}

Jseven_jy 的問題出在他的程序譬如你輸入物品件數3的時候你只能輸入3個重量。
譬如
10
3
1
4
5
你那個有6個，他的程序沒有處理到。所以出錯。算是bug一個。

Jseven_jy : 看不到信息，公司封了只能開到知道和貼吧。其他的全部看不到。

❼ 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);
}

}

❽ 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;