使用蛮力递归解决方案解决 0/1 背包问题的函数

Question

我正在尝试使用此代码使用暴力递归解决方案来解决 0/1 背包问题，但是当我确定问题的大小（利润和重量数组）时，它运行根本没有输出100. 谁能告诉我为什么？以及如何解决。

如果有人能告诉我什么时候可以找到可信的伪代码和 0/1 背包问题的代码，请告诉我。

#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;
//Return the maximum value that can be put in a knapsack of capacity W
int knapsackRecursive(int profits[], int profitsLength, int weights[], int capacity, int currentIndex) {
    // Base Case 
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0)
        return 0;

    //If weight of the nth item is more than knapsack capacity W, then 
    // this item cannot be included in the optimal solgurion
    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);

    //Return the maximum of two cases:
    //(1) nth item included
    //(2) not included

    return max(profit1, profit2);
}

int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
    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++) {      //repeat the knapSack 20 times

        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);      //compute the total cpu time 
    }

    cout << "The avearage of the time taken is" << ((float)timeTaken / CLOCKS_PER_SEC) / 20 << " seconds";



    return 0;
}

Answer 1

将大小设置为 100 只会使它花费太长时间。指数运行时间可不是闹着玩的。

我不知道你的代码是否正确，但只要看看它，我就会发现递归调用的唯一参数是 capacity 和 currentIndex，所以很容易在您的代码中应用 memoization，这将大大加快速度。基本上，记忆只是意味着通过将先前计算的结果存储在 table 中而不是每次都重新计算来重新使用它们。

代码如下：

#include <iostream>
#include <cmath>
#include <tuple>
#include <unordered_map>
#include <functional>

using key_t = std::tuple<int, int>;

struct tuple_hash_t  {
    std::size_t operator()(const key_t& k) const {
        return std::hash<int>{}(std::get<0>(k) ^ std::get<1>(k)); // or use boost::hash_combine
    }
};

using memoization_tbl = std::unordered_map<std::tuple<int, int>, int, tuple_hash_t>;

//Return the maximum value that can be put in a knapsack of capacity W
int knapsackRecursive(memoization_tbl& tbl, int profits[], int profitsLength, int weights[], int capacity, int currentIndex) {

    // Base Case 
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0)
        return 0;

    // just return the memoized call if we already have a result...
    auto iter = tbl.find(key_t(capacity, currentIndex));
    if (iter != tbl.end()) {
        return iter->second;
    }

    //If weight of the nth item is more than knapsack capacity W, then 
    // this item cannot be included in the optimal solgurion
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
        profit1 = profits[currentIndex] + knapsackRecursive(tbl, profits, profitsLength, weights, capacity - weights[currentIndex], currentIndex + 1);

    int profit2 = knapsackRecursive(tbl, profits, profitsLength, weights, capacity, currentIndex + 1);

    //Return the maximum of two cases:
    //(1) nth item included
    //(2) not included

    auto result = std::max(profit1, profit2);
    tbl[key_t(capacity, currentIndex)] = result;

    return result;
}

int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
    memoization_tbl tbl;
    return knapsackRecursive(tbl, profits, profitsLength, weights, capacity, 0);
}

int main() {
    int profits[100];
    int weights[100];
    int capacity = 300;
    srand(time(0));

    for (int j = 0; j < 100; j++) {
        profits[j] = 1 + (rand() % 100);
        weights[j] = 1 + (rand() % 100);
    }

    std::cout << knapSack(profits, 100, weights, capacity) << "\n";

    return 0;
}

使用蛮力递归解决方案解决 0/1 背包问题的函数

function for solving 0/1 knapsack problem using Brute-force recursive solution

c++

recursion

knapsack-problem

brute-force