C语言01背包问题备忘录发

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

1.定义结构体存储物品信息

struct commodity {
    int weight; // 物品重量
    int value; // 物品价值
};

2.定义函数实现01背包问题

int knapsack(struct commodity *commodities, int n, int V) {
    int dp[n + 1][V + 1]; // 定义动态规划数组
    memset(dp, 0, sizeof(dp)); // 初始化为0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < commodities[i - 1].weight) { // 背包容量不足，不能装入第i个物品
                dp[i][j] = dp[i - 1][j];
            } else { // 能装入就比较是否装入第i个物品所得价值大还是不装第i个物品所得价值大
                dp[i][j] = fmax(dp[i - 1][j], dp[i - 1][j - commodities[i - 1].weight] + commodities[i - 1].value);
            }
        }
    }
    return dp[n][V]; // 返回最大价值
}

3.调用函数求解01背包问题

int main() {
    int n = 5; // 物品数量
    int V = 10; // 背包容量
    struct commodity commodities[n] = {{2, 6}, {2, 3}, {6, 5}, {5, 4}, {4, 6}}; // 物品信息
    int max_value = knapsack(commodities, n, V); // 求解01背包问题
    printf("The maximum value is %d\n", max_value); // 输出最大价值
    return 0;
}