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

下面是使用备忘录优化的01背包问题的C语言代码实现：

#include<stdio.h>
#include<string.h>

// 最大物品数量和最大容量
#define MAX_N 100
#define MAX_W 1000

// 物品重量和价值数组
int w[MAX_N], v[MAX_N];

// 备忘录数组
int memo[MAX_N][MAX_W];

// 返回将前i个物品放入容量为j的背包中所能获得的最大价值
int knapsack(int i, int j){
    if(memo[i][j] >= 0){
        // 如果备忘录已经记录了这个状态的值，直接返回备忘录中记录的值
        return memo[i][j];
    }
    int res;
    if(i == 0){
        // 如果已经考虑完了所有的物品，返回0
        res = 0;
    }else if(j < w[i - 1]){
        // 如果背包容量已经不足以放下当前物品，直接跳过当前物品
        res = knapsack(i - 1, j);
    }else{
        // 考虑放入当前物品或者不放入当前物品
        res = max(knapsack(i - 1, j), knapsack(i - 1, j - w[i - 1]) + v[i - 1]);
    }
    // 记录这个状态下的最大价值
    memo[i][j] = res;
    return res;
}

int main(){
    memset(memo, -1, sizeof(memo)); // 初始化备忘录数组为-1
    int n, W;
    scanf("%d%d", &n, &W);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &w[i], &v[i]);
    }
    int ans = knapsack(n, W);
    printf("%d\n", ans);
    return 0;
}

在上述代码中，我们使用了一个二维数组`memo`作为备忘录，其中`memo[i][j]`表示将前i个物品放入容量为j的背包中所能获得的最大价值。在每次递归时，我们首先检查备忘录中是否已经记录了这个状态的值，如果记录了，则直接返回备忘录中记录的值，否则按照普通的01背包算法计算最大价值，并将结果存入备忘录中。

同时，我们在程序开始时使用`memset`函数将备忘录数组初始化为-1，表示这个状态还没有被计算过。