索引问题

Question

我正在编写一个最大值背包算法。它接收一个 Knapsack 对象，其中包含具有价值和成本的 Items。我声明了一个二维数组来计算最大值。对于基本情况，我已将第零行值设置为 0，将第零列值设置为 0。当我在背包中抓取一件物品时，我运行遇到了麻烦，因为当我想抓取第零件物品时，我真的抓住背包中的第一项，并因此在 2D 数组中得到错误的值。有人可以检查我的代码，看看我遗漏了什么吗？

public static double MaximumKnapsack(Knapsack knapsack) {
    int numItems = knapsack.getNumOfItems();
    int budget = (int) knapsack.getBudget();
    double[][] DP = new double[numItems+1][budget+1];

    boolean taken = false;
    for (int i = 0; i < numItems + 1; i++) {
        for (int b = 0; b < budget + 1; b++) {
            if (i == 0 || b == 0) {
                DP[i][b] = 0;
            }
            else
            {
                Item item = knapsack.getItem(i);
                if (item.getCost() > b) {
                    DP[i][b] = DP[i-1][b];
                }
                else
                {
                    DP[i][b] = Math.max(DP[i-1][b-(int) item.getCost()] + item.getValue(),
                                        DP[i-1][b]);
                    if (DP[i][b] == DP[i-1][b-(int) item.getCost()] + item.getValue() && item.getCost() != 0.0) {
                        taken = true;
                    }
                }
            }
        }
        taken = false;
    }
    return DP[numItems][budget];
}

Answer 1

我觉得问题出在

Item item = knapsack.getItem(i);

因为你的循环将从 i = 1 开始。你应该使用：

Item item = knapsack.getItem(i-1);

索引问题

Trouble with indices

knapsack-problem

dynamic-programming

indices