Given a set of items, each with a weight and a value, determine the number of ea

Question

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. This is called knapsack problem. If each item can only be chosen once, then it is called 0-1 knapsack problem. Below is a table shows the weight and value for 8 items, and each item can only be chosen once. The goal is to make the total weight is less than or equal to x, and the total value is as large as possible. A B C D E F G H weight 3 2 5 12 6 9 10 1 value 2 6 0 6 8 0 4 4 (1) Show an example of the encoding vector (2) Show fitness function(two criterion means to check two fitness function)

Explanation / Answer

int max(int a , int b) { if (a>b) { return a; } else { return b; } } //Assuming the weight allowed is W in knapsack and weight and value contain the weights and values of the elements of the knapsack.N is the number of items provided int knapSack(int W, int weight[], int value[], int n) { //If the number of items or the weight allowed is zero if (n == 0 || W == 0) return 0; //if weight of the element is greater than allowed capacity then leave that element and proceed with the next element if (weight[n-1] > W) return knapSack(W, weight, value, n-1); //This is the case when we calculate whether including the element is beneficial or excluding it, hence we calculate maximum of both scenarios else return max( value[n-1] + knapSack(W-weight[n-1], weight, value, n-1), knapSack(W, weight, value, n-1) ); }

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.