01背包带备忘录算法c语言

下面是C语言实现的01背包问题的备忘录算法：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100
#define MAX_W 1000

int N, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N][MAX_W];

int max(int a, int b) {
    return a > b ? a : b;
}

int knapsack(int i, int j) {
    if (dp[i][j] >= 0) return dp[i][j]; // 如果已经计算过，则直接返回结果
    int res;
    if (i == N) {
        res = 0;
    } else if (j < w[i]) {
        res = knapsack(i + 1, j);
    } else {
        res = max(knapsack(i + 1, j), knapsack(i + 1, j - w[i]) + v[i]);
    }
    dp[i][j] = res; // 将计算结果存储在备忘录中
    return res;
}

int main() {
    scanf("%d %d", &N, &W);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = -1; // 初始化备忘录
        }
    }
    printf("%d\n", knapsack(0, W));
    return 0;
}

在该代码中，dp[i][j]表示在前i个物品中选取总重量不超过j的物品的最大价值。在计算dp[i][j]时，如果已经计算过，则直接返回结果；否则，如果第i个物品的重量大于j，则不选第i个物品，直接计算dp[i+1][j]；否则，在选取和不选取第i个物品中取最大值。最后，将计算结果存储在备忘录中，以便之后的计算直接使用。