3

这是一个典型的背包问题，需要动态规划，并且对物品的供应没有限制。我一直在为我的班级研究这个，我尝试了几个小时的算法，但我仍然没有到达那里。

public static int fitBackPack(int[] W, int[] V, int T){
    int[] Opt = new int[T+1];
    Opt[0]=0;
    for (int i=1; i<=T; i++){
        int localMax=0;
        int globalMax=0;
        for (int j=0; j<W.length; j++){
            if (W[j]<=i){
                localMax = (T%W[j]<=W[j]) ?  V[j] : V[j]+Opt[T-W[j]];
                globalMax = (localMax>=globalMax) ? localMax : globalMax;
            }
        }
        Opt[i]=globalMax;
    }
    //debugging purposes
    for (int k=0; k<Opt.length; k++){
        System.out.println("Opt["+k+"] = "+Opt[k]);
    }
    return Opt[T];
}

该方法应该采用 W 和 V 的排序数组，分别包含项目的权重和值，以及表示最大权重的整数 T。对于我的输出，直到 T=21 之前的一切都有效，但是，在那之后它似乎就像一个贪心算法一样工作，这完全不是我所希望的。任何提示将不胜感激，谢谢！

4

2 回答 2

0

提示： (x % y <= y) == true

时不时地通过您的条件和测试用例的真值表将帮助您找到这些。最好还是为一般用途和边缘情况设置一些自动化测试。

于 2012-04-19T01:21:31.683 回答
0

由于你的算法表现得像一个贪心算法，你的问题可能在于计算localMax（因为贪心算法寻找最高的局部值）。通过查看您的代码，您似乎localMax走错了路。提示，见Math.max()函数。

于 2012-04-19T01:40:11.520 回答