暴力递归实现0/1背包问题规模为100时无输出问题咨询

你使用的暴力递归方案属于无优化的穷举思路，每个物品都有「选」和「不选」两种分支，时间复杂度为O(2^n)，n为物品总数。当n=100时，总分支数约为1.27e30，就算当前消费级CPU每秒可以执行1万亿次运算，跑完所有分支也需要数千万亿年，自然会出现长时间无输出的情况。

主流的低复杂度优化方案有两类，均适合你当前的参数规模（n=100，容量=300）：

• 记忆化搜索（自顶向下动态规划）：在原有递归逻辑基础上，增加缓存存储已经计算过的「当前物品索引、剩余容量」对应的最大利润，避免重复计算相同子问题，时间复杂度降至O(nC)（C为背包最大容量），你当前场景总状态数仅为100300=30000，可瞬间完成计算。
• 迭代动态规划（自底向上）：通过数组递推的方式从小到大计算所有子问题的结果，无需递归调用栈开销，还可进一步优化空间复杂度到O(C)。

记忆化搜索实现（基于原有代码修改） #

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

// 记忆化缓存，memo[i][j] 表示从第i个物品开始选，剩余容量j时的最大利润
vector<vector<int>> memo;
int knapsackRecursive(int profits[], int profitsLength, int weights[], int capacity, int currentIndex) {
    // base case
    if (capacity <= 0 || currentIndex >= profitsLength)
        return 0;
    // 已经计算过的状态直接返回缓存结果
    if (memo[currentIndex][capacity] != -1)
        return memo[currentIndex][capacity];
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
        profit1 = profits[currentIndex] + knapsackRecursive(profits, profitsLength, weights, capacity - weights[currentIndex], currentIndex + 1);
    int profit2 = knapsackRecursive(profits, profitsLength, weights, capacity, currentIndex + 1);
    // 结果存入缓存再返回
    memo[currentIndex][capacity] = max(profit1, profit2);
    return memo[currentIndex][capacity];
}

int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
    // 初始化缓存，所有值先设为-1表示未计算
    memo.assign(profitsLength, vector<int>(capacity + 1, -1));
    return knapsackRecursive(profits, profitsLength, weights, capacity, 0);
}

int main() {
    int profits[100];
    int weights[100];
    int capacity = 300;
    srand(time(0));
    clock_t startTime;
    clock_t endTime;
    clock_t timeTaken = 0;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 100; j++) {
            profits[j] = 1 + (rand() % 100);
            weights[j] = 1 + (rand() % 100);
        }
        startTime = clock();
        knapSack(profits, 100, weights, capacity);
        endTime = clock();
        timeTaken = timeTaken + (endTime - startTime);
    }
    cout << "The average of the time taken is " << ((float)timeTaken / CLOCKS_PER_SEC) / 20 << " seconds" << endl;
    return 0;
}

空间优化版迭代DP实现 #

int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < profitsLength; i++) {
        // 倒序遍历容量避免重复选择同一物品
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + profits[i]);
        }
    }
    return dp[capacity];
}

核心伪代码（迭代DP版） #

输入：利润数组profits[0..n-1]，重量数组weights[0..n-1]，背包最大容量C
初始化：一维数组dp[0..C]，所有元素初始值为0
遍历每个物品i从0到n-1：
    遍历容量j从C down to weights[i]:
        dp[j] = max(dp[j], dp[j - weights[i]] + profits[i])
返回dp[C]

内容的提问来源于stack exchange，提问作者hanan