java背包問題,背包問題例子

本文目錄一覽：

• 1、關於這個java語言描述的0-1背包問題是否有錯誤？
• 2、背包問題算法java實現
• 3、_’ title=’回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_’>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_
• 4、java寫背包問題沒看懂
• 5、01背包問題變種：從給定的N個正數中選取若干個數之和最接近M的JAVA寫法
• 6、0-1背包問題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;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;

}

背包問題算法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寫背包問題沒看懂

m[][] 就是一個二維數組。

你平時看見的a[] 這樣的數組是用來定義一維數組的，裏面放的東西你應該明白。二維數組其實和一維數組差不多，只不過二維數組的m[]放的是另外一個m1[]這樣的數組。兩個數組就從線變成了面，類似於XY坐標圖了。這就是二維數組，面上的關係。

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/D20.94;

E1:=(C-HHV(C,12))/HHV(C,12)*10;

E2:=(C-REF(C,26))/REF(C,26)*10;

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)); // 動態規劃表

    }

    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的重量時，能夠獲得的最大價值

                    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]重物獲得的最大價值兩者之間的最大值

                }

            }

        }

        return dp[0][0];

    }

}