背包动态规划

Question

这是一个典型的背包问题，需要动态编程，并且对物品的供应没有限制。我一直在为我的班级做这件事，我试着玩了几个小时的算法，但我仍然没有达到目标。

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工作之前，一切都在工作，然而，在那之后，它似乎就像一个贪婪的算法，这完全不是我所希望的。如有任何提示，我们将不胜感激，谢谢！

Answer 1

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

每隔一段时间，通过包含测试用例的条件的真值表将帮助您找到这些条件。最好还是为一般用法和边缘用例设置一些自动化测试。

Answer 2

由于您的算法行为类似于贪婪算法，因此您的问题可能与localMax的计算有关(因为贪婪算法会寻找最高的局部值)。通过查看您的代码，您似乎以错误的方式获得了localMax。提示，请参见Math.max()函数。