穷举法求解0/1背包问题c语言

穷举法求解0/1背包问题是一种动态规划算法的具体应用，它主要用于优化资源分配问题。在0/1背包问题中，每个物品有其重量w和价值v，目标是在不超过背包容量W的前提下，选择物品使得总价值最大。在C语言中，可以按照以下步骤实现：

1. 定义一个二维数组dp，其中dp[i][j]表示前i个物品放入容量为j的背包可以获得的最大价值。

2. 初始化：对于dp[0][j]（即空背包），其值为0；对于dp[i][0]（即无法放置物品时），其值为0（因为没有物品，自然价值为0）。

3. 状态转移方程：对于每个物品i和每个可能的背包容量j，有两种情况：
- 如果物品i的重量大于当前背包容量j，则不能包含该物品，取状态转移为dp[i-1][j]；
- 否则（物品i的重量小于等于j），可以选择包含或不包含，包含的话价值为dp[i-1][j-w[i]] + v[i]，不包含的话还是原来的dp[i-1][j]，取两者中的较大值。

4. 遍历所有物品和背包容量，更新dp数组。

5. 最终的解就是dp[n][W]，其中n是物品的数量。

#include <stdio.h>

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n+1][W+1];

    // 初始化
    for (i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (w = 1; w <= W; w++) {
        dp[0][w] = 0;
    }

    // 动态规划计算
    for (i = 1; i <= n; i++) {
        for (w = 1; w <= W; w++) {
            if (wt[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50, wt[] = {10, 20, 30}, val[] = {60, 100, 120}, n = sizeof(wt)/sizeof(wt[0]);
    printf("最大价值为: %d\n", knapsack(W, wt, val, n));
    return 0;
}