0/1 背包问题动态规划解法及代码优化

0/1 背包问题是经典的动态规划问题之一，它描述了以下场景：给定 n 个物品和一个容量为 W 的背包，每个物品有对应的重量 w 和价值 v，如何选择物品放入背包，使得背包中物品的总价值最大？

动态规划解法

动态规划解法使用一个二维数组 dp[i][j] 来存储从前 i 个物品中选择，背包容量为 j 时所能获得的最大价值。其递推公式为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

其中：

dp[i-1][j] 表示不选择第 i 个物品时的最大价值
dp[i-1][j-w[i]] + v[i] 表示选择第 i 个物品时的最大价值

代码实现

#include <stdio.h>
#include <stdbool.h>
#include <time.h>

// 定义最大物品数量和背包容量
#define MAX_ITEMS 100
#define MAX_CAPACITY 100

// 返回两个数中的最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 动态规划解决0/1背包问题
int knapsack(int weights[], int values[], int n, int capacity, int selected_items[]) {
    // 创建一个二维数组来保存最优解
    int dp[MAX_ITEMS + 1][MAX_CAPACITY + 1];

    // 创建一个二维数组来保存是否选取该物品
    bool selected[MAX_ITEMS + 1][MAX_CAPACITY + 1];

    // 初始化第一行和第一列为0
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
        selected[i][0] = false;
    }
    for (int j = 0; j <= capacity; j++) {
        dp[0][j] = 0;
        selected[0][j] = false;
    }

    // 使用动态规划计算最优解
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            // 如果当前物品重量小于等于背包容量
            if (weights[i - 1] <= j) {
                // 更新最优解
                if (values[i - 1] + dp[i - 1][j - weights[i - 1]] > dp[i - 1][j]) {
                    dp[i][j] = values[i - 1] + dp[i - 1][j - weights[i - 1]];
                    selected[i][j] = true;
                } else {
                    dp[i][j] = dp[i - 1][j];
                    selected[i][j] = false;
                }
            } else {
                // 当前物品重量大于背包容量，无法放入背包
                dp[i][j] = dp[i - 1][j];
                selected[i][j] = false;
            }
        }
    }

    // 输出最优解时背包所装物品的序号
    int index = 0;
    int i = n;
    int j = capacity;
    while (i > 0 && j > 0) {
        if (selected[i][j]) {
            selected_items[index++] = i;
            j -= weights[i - 1];
        }
        i--;
    }

    // 返回最优解
    return dp[n][capacity];
}

int main() {
    // 物品重量和价值数组
    int weights[MAX_ITEMS];
    int values[MAX_ITEMS];
    int n;
    int capacity;

    // 从键盘输入物品数量和背包容量
    printf('请输入物品数量：');
    scanf('%d', &n);
    printf('请输入背包容量：');
    scanf('%d', &capacity);

    // 从键盘输入物品重量和价值
    printf('请输入物品重量：\n');
    for (int i = 0; i < n; i++) {
        scanf('%d', &weights[i]);
    }
    printf('请输入物品价值：\n');
    for (int i = 0; i < n; i++) {
        scanf('%d', &values[i]);
    }

    // 获取程序运行前的时间
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    // 求解0/1背包问题
    int selected_items[MAX_ITEMS];
    int result = knapsack(weights, values, n, capacity, selected_items);

    // 获取程序运行后的时间
    clock_gettime(CLOCK_MONOTONIC, &end);
    double time_taken = (end.tv_sec - start.tv_sec) * 1000.0 + (end.tv_nsec - start.tv_nsec) / 1000000.0;

    // 按顺序输出物品序号
    printf('背包所装物品序号：');
    for (int i = result - 1; i >= 0; i--) {
        printf('%d ', selected_items[i]);
    }
    printf('\n');

    // 输出结果和程序运行时间
    printf('背包问题最优解: %d\n', result);
    printf('程序运行时间: %.2f毫秒\n', time_taken);

    return 0;
}

代码优化

顺序输出物品序号：在knapsack函数中，新增一个数组selected_items来保存选择的物品序号，并将选取的物品序号保存到该数组中。在main函数中，反向遍历selected_items数组来按顺序输出物品序号。

时间复杂度

该算法的时间复杂度为 O(nW)，其中 n 为物品数量，W 为背包容量。

示例程序

输入：

物品数量：5

背包容量：10

物品重量：2 3 4 5 6

物品价值：3 4 5 6 7

输出：

背包所装物品序号：4 3 1

背包问题最优解: 14

程序运行时间: 0.01毫秒

总结

本文介绍了使用动态规划算法解决 0/1 背包问题，并优化代码使其能够按顺序输出所选物品序号。代码附带时间复杂度分析，并提供示例程序，帮助读者理解该算法并进行实际应用。