背包问题的记忆解决方案输出错误

Question

我需要通过递归、记忆和动态规划来解决背包问题。目前我停留在 memoized 方法（部分是动态编程方法）。

我根据我在互联网上其他地方找到的代码改编了代码。目前输出不正确。

问题涉及利润和质量。每个项目都有一个利润和质量相关联，有 MAX_N（数量）可用项目和 MAX_CAPACITY 质量。目的是让背包里的东西尽可能多"profit"

这是练习提供的示例：

Example: Given a knapsack of capacity 5, and items with mass[] = {2, 4, 3, 2} and profit profit[] = {45, 40, 25, 15}, the best combination would be item 0 (with mass 2 and profit 45) and item 2 (with mass 3 and with profit 25) for a total profit of 70. No other combination with mass 5 or less has a greater profit.

完整代码如下：

#include <stdio.h>

#define MAX_N 10
#define MAX_CAPACITY 165

int m[MAX_N+1][MAX_CAPACITY+1];

int max(int x, int y) {
    return x ^ ((x ^ y) & -(x < y));
}

int min(int x, int y) {
    return y ^ ((x ^ y) & -(x < y));
}

int knapsackRecursive(int capacity, int mass[], int profit[], int n) {

    if (n < 0)
        return 0;

    if (mass[n] > capacity)
        return knapsackRecursive(capacity, mass, profit, n-1);

    else
        return max(knapsackRecursive(capacity, mass, profit, n-1), knapsackRecursive(capacity - mass[n], mass, profit, n-1) + profit[n]);

}

int knapsackMemoized(int capacity, int mass[], int profit[], int n) {

    int take = 0;
    int dontTake = 0;

    if (m[n][capacity] != 0)
        return m[n][capacity];

    if (n == 0) {

        if (mass[0] <= capacity) {
            m[n][capacity] = profit[0];
            return profit[0];
        }

        else {
            m[n][capacity] = 0;
            return 0;
        }
    }

    if (mass[n] <= capacity)
        take = profit[n] + knapsackMemoized(capacity-mass[n], mass, profit, n-1);

    dontTake = knapsackMemoized(capacity, mass, profit, n-1);

    m[n][capacity] = max(take, dontTake);

    return m[n][capacity];

}

int knapsackDynamic(int capacity, int mass[], int profit[], int n) {

    // this only works with int m[MAX_N+1][MAX_CAPACITY+1];

    int i;
    int j;

    for (i = 0; i <= n; i++) {

        for (j = 0; j <= capacity; j++) {

            if (i == 0 || j == 0)
                m[i][j] = 0;

            else if (mass[i-1] <= j)
                m[i][j] = max(profit[i-1] + m[i-1][j-mass[i-1]], m[i-1][j]);

            else
                m[i][j] = m[i-1][j];
        }
    }

    return m[n][capacity];

}

void test() {

    // test values
    //int M1[MAX_N] = {2, 4, 3, 2};
    //int P1[MAX_N] = {45, 40, 25, 10};

    int M1[MAX_N] = {6, 3, 2, 4};
    int P1[MAX_N] = {50, 60, 40, 20};

    int M2[MAX_N] = {23, 31, 29, 44, 53, 38, 63, 85, 89, 82};
    int P2[MAX_N] = {92, 57, 49, 68, 60, 43, 67, 84, 87, 72};

    // a)
    printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M1, P1, MAX_N));
    printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M2, P2, MAX_N));
    printf("\n");

    // b)
    printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M1, P1, MAX_N));
    printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M2, P2, MAX_N));
    printf("\n");

    // c)
    printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M1, P1, MAX_N));
    printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M2, P2, MAX_N));

}

int main() {
    test();
}

这是输出：

Recursion: 170
Recursion: 309

Memoization: 170
Memoization: 170

Dynamic Programming: 170
Dynamic Programming: 309

Process returned 25 (0x19)   execution time : 0.014 s
Press any key to continue.

如您所见，递归和动态规划解决方案提供了正确的输出。（我通过函数检查了运行给定的示例数组。）记忆方法目前没有。事实上，它总是为两个阵列提供相同的结果，老实说，我对此感到很困惑。

另一个问题（尽管远没有那么大）是动态规划方法仅适用于 int m[MAX_N+1][MAX_CAPACITY+1];，但练习需要 int m[MAX_N][MAX_CAPACITY];。我不确定如何更改代码以支持后者。

Answer 1

所以我知道这是一道作业题，所以我不会给出正确答案，但我可以这样说：

如果一个函数在第二次运行时返回相同的答案，这通常是因为某些东西没有归零。前一个运行.

留下了一些污垢

检查您假设在函数范围之外创建的变量应该是干净的所有地方。

编辑：对于你的第二个问题，m[ITEM][CAP] 是一个矩阵，反映每个项目剩余的每个上限的利润。这些项目是一个循环，运行遍历所有项目一次。 1 to MAX 或 0 to (MAX-1)，即具有 MAX 个单元格的数组。每个项目的上限可以是 0 to MAX_CAP 之间的所有内容。该范围是 MAX_CAP+1 长，这意味着您需要创建 int m[MAX_N][MAX_CAPACITY+1]。我认为不可能以其他方式做到这一点，您的代码应该已经适用于此。

背包问题的记忆解决方案输出错误

wrong output for memoization solution of knapsack issue

c

knapsack-problem

memoization

dynamic-programming