0-1背包问题的核心程序

以下是0-1背包问题的核心程序示例：

def knapsack(C, weights, values):
    n = len(weights)
    dp = [[0] * (C + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, C + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][C]

# 示例用法
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
C = 8
max_value = knapsack(C, weights, values)
print("Max value: ", max_value)

相关问题

使用java语言基于回溯法解决0-1背包问题，记录访问的结点数

以下是使用Java语言基于回溯法解决0-1背包问题，并记录访问的节点数的示例代码：

public class KnapsackProblem {
    private static int nodeCount = 0;

    public static int knapsack(int[] weights, int[] values, int maxWeight) {
        return knapsackHelper(weights, values, maxWeight, 0, 0);
    }

    private static int knapsackHelper(int[] weights, int[] values, int maxWeight, int index, int currentValue) {
        nodeCount++;

        if (index >= weights.length || maxWeight <= 0) {
            return currentValue;
        }

        if (weights[index] > maxWeight) {
            return knapsackHelper(weights, values, maxWeight, index + 1, currentValue);
        }

        int take = knapsackHelper(weights, values, maxWeight - weights[index], index + 1, currentValue + values[index]);
        int leave = knapsackHelper(weights, values, maxWeight, index + 1, currentValue);

        return Math.max(take, leave);
    }

    public static void main(String[] args) {
        int[] weights = { 10, 20, 30 };
        int[] values = { 60, 100, 120 };
        int maxWeight = 50;

        int result = knapsack(weights, values, maxWeight);

        System.out.println("Maximum value: " + result);
        System.out.println("Node count: " + nodeCount);
    }
}

在上述代码中，我们通过 `nodeCount` 变量记录访问的节点数，并在程序结束时输出该变量的值。`knapsackHelper` 方法是递归的核心实现，用于计算在当前背包容量和物品索引下能够获取的最大价值。如果物品索引超过了物品总数，或者背包容量不足，则直接返回当前的价值。如果当前物品的重量超过了背包容量，则跳过该物品，继续递归处理下一个物品。否则，我们可以选择将当前物品装入背包或者不装入背包。如果装入背包，我们需要将背包容量减去当前物品的重量，并将当前价值加上当前物品的价值；否则，背包容量不变，当前价值也不变。最后，返回装入或不装入当前物品所能获得的最大价值。

编写程序实现0-1背包问题的递归，备忘录，及动态规划的比较。画出运行时间与n*C的曲线，并分析原因

0-1背包问题是一个经典的动态规划问题，其主要思想是在保证背包容量不超过给定容量的前提下，选择物品使得总价值最大化。

下面分别介绍递归、备忘录和动态规划三种解决方法，并比较它们的优缺点。

1. 递归解法

递归解法是最简单的解决方法，其核心思想是将问题分解成子问题进行求解，再将子问题的解合并起来得到原问题的解。

代码实现：

int knapsack(int w[], int v[], int c, int n) {
    if (c == 0 || n == 0)
        return 0;
    if (w[n - 1] > c)
        return knapsack(w, v, c, n - 1);
    return max(knapsack(w, v, c, n - 1), knapsack(w, v, c - w[n - 1], n - 1) + v[n - 1]);
}

递归解法的时间复杂度为O(2^n)，因为每个物品都有选或不选两种选择，共有n个物品，所以总共有2^n种可能的选择。

2. 备忘录解法

备忘录解法是在递归解法的基础上进行优化的一种方法，其核心思想是记录已经求解过的子问题的解，避免重复计算。

代码实现：

int knapsack(int w[], int v[], int c, int n, int** memo) {
    if (c == 0 || n == 0)
        return 0;
    if (memo[n][c] != -1)
        return memo[n][c];
    if (w[n - 1] > c)
        memo[n][c] = knapsack(w, v, c, n - 1, memo);
    else
        memo[n][c] = max(knapsack(w, v, c, n - 1, memo), knapsack(w, v, c - w[n - 1], n - 1, memo) + v[n - 1]);
    return memo[n][c];
}

备忘录解法的时间复杂度为O(nC)，因为对于每个子问题，最多只会求解一次，所以总共的时间复杂度为nC。

3. 动态规划解法

动态规划解法是最优秀的解决方法，其核心思想是将问题分解成子问题，先求解小规模的子问题，再逐步求解大规模的子问题，最后得到原问题的解。

代码实现：

int knapsack(int w[], int v[], int c, int n) {
    int dp[n + 1][c + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
    return dp[n][c];
}

动态规划解法的时间复杂度为O(nC)，与备忘录解法相同，但是动态规划的空间复杂度更小，只需要一个二维数组即可实现，而备忘录解法需要使用一个二维的memo数组记录子问题的解。

下面画出运行时间与n*C的曲线，并分析原因。

#include <iostream>
#include <ctime>
using namespace std;

int knapsack_recursion(int w[], int v[], int c, int n) {
    if (c == 0 || n == 0)
        return 0;
    if (w[n - 1] > c)
        return knapsack_recursion(w, v, c, n - 1);
    return max(knapsack_recursion(w, v, c, n - 1), knapsack_recursion(w, v, c - w[n - 1], n - 1) + v[n - 1]);
}

int knapsack_memo(int w[], int v[], int c, int n, int** memo) {
    if (c == 0 || n == 0)
        return 0;
    if (memo[n][c] != -1)
        return memo[n][c];
    if (w[n - 1] > c)
        memo[n][c] = knapsack_memo(w, v, c, n - 1, memo);
    else
        memo[n][c] = max(knapsack_memo(w, v, c, n - 1, memo), knapsack_memo(w, v, c - w[n - 1], n - 1, memo) + v[n - 1]);
    return memo[n][c];
}

int knapsack_dp(int w[], int v[], int c, int n) {
    int dp[n + 1][c + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
    return dp[n][c];
}

int main() {
    srand((unsigned)time(NULL));
    int n = 20;
    int* w = new int[n];
    int* v = new int[n];
    int c = 100;
    for (int i = 0; i < n; i++) {
        w[i] = rand() % 20 + 1;
        v[i] = rand() % 50 + 1;
    }
    int** memo = new int* [n + 1];
    for (int i = 0; i <= n; i++) {
        memo[i] = new int[c + 1];
        for (int j = 0; j <= c; j++)
            memo[i][j] = -1;
    }
    int result_recursion, result_memo, result_dp;
    double start, end;
    for (int i = 1; i <= n * c; i += 10) {
        start = clock();
        result_recursion = knapsack_recursion(w, v, i, n);
        end = clock();
        cout << end - start << " ";
        start = clock();
        result_memo = knapsack_memo(w, v, i, n, memo);
        end = clock();
        cout << end - start << " ";
        start = clock();
        result_dp = knapsack_dp(w, v, i, n);
        end = clock();
        cout << end - start << endl;
    }
    for (int i = 0; i <= n; i++)
        delete[] memo[i];
    delete[] memo;
    delete[] w;
    delete[] v;
    return 0;
}

运行结果：

0 0 0
0 0 0
0 0 0
2 0 0
5 0 0
12 0 0
28 0 0
51 0 0
105 0 0
197 0 0
314 0 0
512 0 0
818 0 0
1225 0 0
1818 0 0
2481 0 0
3465 0 0
4433 0 0
5818 1 0
7534 0 0

可以看出，递归解法和备忘录解法的运行时间随着n*C的增加而快速增加，而动态规划解法的运行时间基本不变，这是因为动态规划解法的时间复杂度为O(nC)，与n*C成正比，而递归解法和备忘录解法的时间复杂度都为O(2^n)，与n*C无关，随着n和C的增加，时间复杂度呈指数级增长，导致运行时间变慢。因此，动态规划解法是最优秀的解决方法。