0

i modified some code from internet to meet my requirements, but unfortunately this program seems to run a bit slow. im not sure whether its my computer or the program itself is slow.

   int max(int a, int b)
{
    return (a > b) ? a : b;
}

int knapSack(int W, int wt[], int val[], int n)
{

    if (n == 0 || W == 0)
        return 0;


    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);

    else
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
                knapSack(W, wt, val, n - 1));
}


int main()
{
        char exeAgain='n';

        do
        {

        cout << "Enter the number of items in a Knapsack : ";
        int n, W;
        cin >> n;
        int val[n], wt[n];
        for (int i = 0; i < n; i++)
        {
            val[i]=(rand()%100)+1;
            wt[i]=(rand()%100)+1;
            cout << "Item Number "<< i+1 << " value "<<val[i]<<" weight " << wt[i] << endl;

        }


        cout << "Enter the capacity of knapsack : ";
        cin >> W;
        cout << "The total profit is " << knapSack(W, wt, val, n)<< endl;

        cout<<"Would you like to execute this program again? [Y/N] : ";
        cin>>exeAgain;
        }
        while(exeAgain == 'y' || exeAgain == 'Y');

    return 0;
}

is it normal for this program to run slow? (the input is 200 & 1500) smaller input is fast, but when i use big number, the program slows down.

1
  • Learn what the program is doing an trace it in a debugger.
    – Jan Doggen
    Sep 13, 2015 at 17:11

1 Answer 1

0

The Knapsack Problem is famously NP-Complete, which means in simple terms that as the size of your input increases, the time to solve it increases astronomically. So yes, it is completely normal for your program to run slowly at larger inputs.

If you research around, you'll find a lot of work done on the problem, including various strategies to run faster than a first attempt, or heuristics for a good-but-not-perfect solution, which will run faster than something looking for a perfect solution.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.