Question

create a genetic algorithm for knapsack problem in c++

Answer 1

Knapsack problem can be understand by following problem:

A thief is robbing a store and can carry a max_imal weight of W into his knapsack. There are n items and weight of ith item is wi and the profit of selecting this item is pi. What items should the thief take?

Hence solution is which to take and what to leave. To solve we choose only those item of max value or profit.

To consider all subsets of items, there can be two cases for every item:

I. Include item as optimal as solution part

II. Don't consider as solution part..

Therefore, the maximum value / profit that can be obtained from n items is max of following two values.
a) Maximum value / result  by n-1 items and W weight (excluding nth item).
b) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

for Value[] = { 60, 100, 120 }
and profit [] = { 10, 20, 30 }

Using 0/1 Knapsack solution approach,
solution leads to following view with optimal solution
weight : 10 ==> Value : 60
Weight : 20 ==> Value : 100
Weight : 30 ==> Value: 120
Weight: 20 & 10 ==> Value ( 120)
and similarly finally,
Weight: 30 & 20 will give 120 + 100 = 220 which is max profitable value.

In this way, problem is solved.

C++ implementation is following:

int KNAP_SACK(int W, int wt[], int val[], int n)

{

if (n == 0 || W == 0)      return 0; // This is base case of recursive approach

  

// Else select the max giving value recursively, until base is not returned

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

else return max( val[n-1] + KNAP_SACK(W-wt[n-1], wt, val, n-1),

KNAP_SACK(W, wt, val, n-1) );

}