背包问题的java代码,背包问题的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）

相关问答

Q1: 关于这个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;

}

Q2: 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];

    }

}