Question

回溯法解决0-1背包问题 java写的 求大神指点~~~~(>_<)~~~~

代码：

import java.util.*;
public class Main {
static int n;
static int c;
static int[] v = new int[n];
static int[] w = new int[n];
static int bestp=0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
n = input.nextInt();
c = input.nextInt();
for(int i=0; i<v.length; i++)
v[i] = input.nextInt();
for(int i=0; i<w.length; i++)
w[i] = input.nextInt();

Backtrack(0);
System.out.println(bestp);
}
public static int Bound(int i)
{
int b=0;
int j;
for(j=i;j<n;j++) b+=v[j];
return b;
}
public static void Backtrack(int i){
int cw=0;
int cp=0;
if(i>=n){
bestp=cp;
return;
}
if(cw+w[i]<=c){
cw+=w[i];
cp+=v[i];
Backtrack(i+1);
cw-=w[i];
cp-=v[i];
}
if(cp+Bound(i+1) > bestp)
Backtrack(i+1);
}
}

但出现
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
at javaapplication43.Main.Backtrack(Main.java:36)
at javaapplication43.Main.main(Main.java:19)
Java Result: 1

Answer 1

因为你把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）

Answer 2

把这两行代码
static int[] v = new int[n];
static int[] w = new int[n];
放在
n = input.nextInt();
c = input.nextInt()
后面

追问

thank you, too