Problem 2 [50 points] Consider the following more general version of the Knapsac
ID: 3710622 • Letter: P
Question
Problem 2 [50 points] Consider the following more general version of the Knapsack problem There are p groups of objects O1, O2,.. , Op and a knapsack capacity W. Each object x has a weight w and a value vx. Our goal is to select a subset of objects such that: the total weights of selected objects is at most W, at most one object is selected from any group, and the total value of the selected objects is maximized. Suppose that n is the total number of objects in all the groups and V is the maximum value of vg. Give an O(nW) time algorithm for this general Knapsack any object, ie., V-max problem. Explain why your algorithm is correct and analyze the running time of your algorithm. Hint: Do a dynamic programming with increasing Knapsack capacity x is an objectExplanation / Answer
Select_val(wt[],val[],group[],n)
{
Group_selected[p]
for(i?1;i<p;i++)
Group_selected[i]?false
Selecect maximum value of ratio val[i]/wt[i] from each group
j?1
for(i?1;i<n;i++)
k?i
if(group[i]=group[i+1])
k?max( val[i]/wt[i], val[i+1]/wt[i+1])
else
val[j] ?val[k]
val[j] ?val[k]
Group_selected[i]?true
j?j+1
if(group[i] !=group[i-1])
val[j] ?val[i]
val[j] ?val[i]
//implicitely return value of v[] and wt[]
}
knapSack(W, wt[], val[],group[], n,p)
{
i, w,K[p+1][W+1]
//SELECT the item with maximum ratio val[i]/wt[i] from each group of item
Select_val(wt,val,group,n)
// Build table K[][] in bottom up manner
for (i = 1; i <= p+1; i++)
{
for (w = 1; w <= W+1; w++)
{
if (i==1 || w==1)
K[i][w] = 0;
else if ((wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
Time complexity: time complexity of Select_val(wt,val,group,n) is O(n)
And knapsack O(n)+ O(pW) which is always less than O(nW). Algorithm works correctly because each loop is initialized, incremented and checked for termination.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.