Question

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, and 70} and values {70, 80, 90, and 200}. Apply the brute force algorithm to find the maximum value of the items you can carry using the knapsack?

Answer 1

The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.

#include <bits/stdc++.h> 
using namespace std; 
int knapSack(int W, int wt[], int val[], int n) 
{ 

        if (n == 0 || W == 0) 
                return 0; 
        if (wt[n] > W) 
                return knapSack(W, wt, val, n - 1); 
        else
        if ( val[n] + knapSack(W - wt[n], wt, val, n - 1) > knapSack(W, wt, val, n - 1))
            return val[n] + knapSack(W - wt[n], wt, val, n - 1)
        else
            return knapSack(W, wt, val, n - 1)
                
} 

int main() 
{ 
        int val[] = { 70, 80, 90 ,200 }; 
        int wt[] = { 20, 30 ,40 ,70 }; 
        int W = 60; 
        int n = sizeof(val) / sizeof(val[0]); 
        cout << knapSack(W, wt, val, n); 
        return 0; 
}