Question

C++ This needs to be a recursive combinational array please. This NEEDS to be recursive and no vectors. Thank you

Write a program that solves the knapsack problem recursively for an arbitrary knapsack capacity and series of weights. Assume the weights are sorted in an array. Hint: The arguments to the knapsack function are target weight and the array index where the remaining items start. The knapsack problem in its simplest form involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You need to fit in all items. For example if you want your knapsack to weigh exactly 20 pounds and you have five items with weights of 11,8,7,6 and 5 pounds. In this case only combination that works is 8, 7 and 5 pounds.

Answer 1

The Knapsack problem is a combitoraial optimization problem used to show  both problem and solution.It can be solved by greedy method approach.

In 0-1 knapsack problem, a set of items are given, each with a weight and a value. We need to determine the number of each item to include in a collection so that the total weight is less than or equal to the given Weight and the total value is large as possible.

/* A  recursive implementation of Knapsack problem using array */

#include <bits/stdc++.h> 
using namespace std; 
  

int maximum(int a, int b) { return (a > b) ? a : b; } 
  
// Returns the maximum value that 
 
int knapSack(int W, int weight[], int values[], int n) 
{ 
  
    // Base Case 
    
    if (n == 0 || W == 0) 
        return 0; 
  
    // If weight of the nth item is more 
    // than Knapsack capacity W, then 
    // this item cannot be included 
    // in the optimal solution 
    
    if (weight[n] > W) 
        return knapSack(W, weight, values, n - 1); 
  
     
    else
        return maximum( 
            values[n] + knapSack(W - weight[n],  
                                    weight, values, n - 1), 
            knapSack(W, weight, values, n - 1)); 
} 
  
// Driver code 

int main() 
{ 
    int values[] = { 10, 20, 30, 10, 50 };  //values of the items
    int weight[] = { 11, 8, 7, 6, 5 };       // values of the weight given
    
    int W = 20;    //capacity of weight
    
    int n = sizeof(values) / sizeof(values[0]); 
    cout << " knapSack value is " << knapSack(W, weight, values, n); 
    
    return 0; 
}

OUTPUT:-

value[] = { 10, 20, 30, 10, 50} Weight= 11; Value=10; And here the Combination that works is--

weight[] = { 11, 8, 7, 6, 5 }   Weight= 8; Value=20; Weight=( 8+7+5 ); Value=(20+30+50);

W = 20   Weight= 7; Value=30;

solution : 100   Weight= 6; Value=10;

  Weight= 5; Value=50;

  

--------------------------------------------------Thank You---------------------------------------------------------------------------