I am trying this code for solving 0/1 knapsack problem using Brute-force recursive solution, but it keeps running with no output at all when I make the size of the problem(profit and weight arrays) 100. if any one can tell me why? and how to solve it.

Please if any one can tell me when to find trusted pseudocodes and codes for 0/1 knapsack problem.

#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;
}

CodePudding user response：

Setting the size to 100 just makes it take too long. Exponential running times are no joke.

I have no idea if your code is correct but just looking at it I can see that the only arguments to the recursive call that ever change are capacity and currentIndex so it is easy to apply memoization in your code, which will be a huge speed-up. Basically "memoization" just means re-using previously computed results by storing them in a table rather than re-computing every time.

Code below:

#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;
}