There are n items in a store. For each item i=1,2,...,n the weight of the item i

ID: 666625 • Letter: T

Question

There are n items in a store. For each item i=1,2,...,n the weight of the item is wi and the value of the item is vi. A thief is carrying a knapsack of weight W. In this version of a problem the items can be broken into smaller pieces, so the thief may decide to carry only a fraction xi of object i, where 0xi 1. Item i contributes xiwi to the total weight in the knapsack, and xivi to the value of the load. Find the maximum value that the thief can fill in his knapsack. Part A: (20%)Write pseudocode for the algorithm to solve this problem. Part B: (5%)What is the complexity of this algorithm? Part C: (5%)What is the archetype of this algorithm?

Explanation / Answer

FOR i =1 to n
do x[i] =0
weight = 0
while weight < W
do i = best remaining item
IF weight + w[i] W
then x[i] = 1
weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = W
return x

B.#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define N 100 // maximum number of items
long i,k,l,n,vi[N],wi[N],W;
double weight,x[N];
typedef pair < double ,long> obj;

int main()
{
/****/
while(printf("Input number of items(EOF to terminate) : "),~scanf("%ld",&n))
{

vector<obj>V;
printf("Input maximum weight can carry : ");
scanf("%ld",&W);

for(i=0;i<n;i++)
{
scanf("%ld%ld",&wi[i],&vi[i]);
//Input weight & value for n number of Items

V.push_back(obj(((double)vi[i]/(double)wi[i]),i));
}

/****knapscak algo******/

sort(V.begin(),V.end());// Sort according to vi[]/wi[];

for(i=0;i<n;i++)
x[i]=0.000;//i have not used the ith object yet

weight=0; // no item is in the bag yet
double value=0,total=0;

long j=n-1; //best are in decreasing order in the vector
while(weight<W && j>=0)
{
i=V[j--].second;// i is best remaining item

if(weight+wi[i]<=W)//we can take the full item
{
x[i]=1;
weight+=wi[i];
value+=vi[i];
}
else{// need to take fraction of ith item
x[i]=double(W-weight)/(double)wi[i];
value+=vi[i]*x[i];
weight=W;
}
}

cout<<"Total value of the taken items : "<< value << endl;

/*********/
}
return 0;
}

If the items are already sorted into decreasing order of vi / wi, then
the while-loop takes a time in O(n);
Therefore, the total time including the sort is in O(n log n).

Navigate

There are n animals who are sick and need to see a doctor. Each animal belongs t

There are n male students and m female students. A male student and a female stu

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

There are n items in a store. For each item i=1,2,...,n the weight of the item i

Question

Explanation / Answer

Related Questions

Navigate