整数背包问题 动态规划 递推公式c语言

下面是整数背包问题的动态规划递推公式的C语言实现：

#include <stdio.h>

// 背包容量
#define CAPACITY 10
// 物品数量
#define N 5

// 物品重量
int weight[N] = {2, 2, 6, 5, 4};
// 物品价值
int value[N] = {6, 3, 5, 4, 6};

// 动态规划数组
int dp[CAPACITY + 1] = {0};

int main() {
    // 逐个考虑每个物品
    for (int i = 0; i < N; i++) {
        // 逆序遍历背包容量，保证每个物品只能放一次
        for (int j = CAPACITY; j >= weight[i]; j--) {
            // 如果当前背包容量可以放下物品i
            if (j >= weight[i]) {
                // 如果放下物品i的价值比不放物品i的价值高
                if (dp[j - weight[i]] + value[i] > dp[j]) {
                    // 则更新当前背包容量的最大价值
                    dp[j] = dp[j - weight[i]] + value[i];
                }
            }
        }
    }

    // 输出最大价值
    printf("%d\n", dp[CAPACITY]);

    return 0;
}