Question

2 Knapsack Problem În al Knapsack problem. given n items(11-12. . . . . 1"} with weight {w1·W2. . . . . ux) and value (n 2, .., nJ, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity In this question, we will consider two different ways to represent a solution to the Knapsack problem using . an array with size n: X-r1.z2····.znl . linked list L that stores the indices of items that are included in a solution. For example, if a solution only includes items I2, I3 and Is, the binary array representation will be 0, 1, 1,0, 1,0,0 and the linked list representation will be head-2+3-+5 [4 marks You decide to use a Monte Carlo-style simulation approach to invest igate possible solutions to the Knapsack problem. In this approach, you randomly generate m feasible solu- tions {X1 , X2, . . . , Xm) with objective values {Vi, 2, . .. , V..), where X, can be represented using either an array or list as described above. (a) Write a function CoMPUTEMEAN(argument list) to calculate the mean value of each variable Tj (j-: 1, 2, . . . ,n) in the given m samples: j,-m Σml XiLi]. Note the format of the argument list will depend on the representation you have selected Full marks will be given if your algorithm runs in 0(Σ㈡ ,I) time, where L1 denotes the size of the linked list representation of X (b) 2 marks Briefly describe how a greedy algorithm (heuristic) could be developed for solving the Knapsack problem using the COMPUTEMEAN) function. ·You do not have to write an algorithm in pseudo code to answer part (b) of this ques- tion. We are expecting that you write a short paragraph or a short list of bullet points describing the important steps of the algorithm . You should also comment on whether such a greedy approach would be effective.

l have posted it a few times before but didnt get a satisfactory answer. kindly help me by answering in pseudo code

Answer 1

Here I have assumed the list representation to be of an array type.

So therefore for compute mean, for each would be adding the respective values of at ith place in all the arrays.

I am using MATLAB as a basic language to write the pseudocode for COMPUTEMEAN.

In Matlab, the list of arrays are merged together in the form of a matrix such that the row denotes one array, and the matrix would be of the size (mXn). After this, we can apply the mean function on the columns of the matrix and thus get a vector having the mean as needed.

Following is the code for the approach.

function values_mean= COMPUTEMEAN(list){ %list is the list of m arrays as feasible solutions

2d_list = [X1; X2; X3;.......;Xm] %Here the ';' is important. m is already known before, this will create the req matrix

%Applying mean to the columns of the matrix

values_mean = mean(2d_list);

%This function returns the mean of each column in a row vector called values mean

}

Now for the greedy algorithm for this problem, we need to have a heuristic, i.e. we need to have a single measure which can be maximized and taken. Now in a normal greedy approach, we use value/weight ratio and the max ration is preferred first so that we have the best possible solution.

However here the question asks to use ComputeMean() in the greedy problem (heuristic). Now let's see what does the computeMean return to us exactly.

The computeMean method implemented above would return a row vector consisting of values between 0 and 1. This is because all values in the array representation are 0 or 1 so the mean of them is going to be somewhere in between. So each element in the returning vector can be said to be the likelihood of that element to be in the final solution.

So here, we can have ComputedMean as a heuristic measure. We can select those items which have a high computedMean value and keep doing so until the knapsack capacity is reached. That would give us a solution to the knapsack problem.

The effectiveness of such a greedy approach would depend highly on the success of Monte Carlo-style simulation approach that will return a list of feasible solutions. If the list of feasible solutions is close enough to the real solution then this method will succeed. Otherwise, the answer would be wrong. Therefore it can be concluded that this method can only be used if we have a list of correct feasible solutions possible.

If you have any doubts, please comment below.

If the answer helped you, please leave a thumbs up :)