The knapsack problem with 2 parameters is very close to the knapsack probelm with 1 parameter.
The problem is as follows
We have a bag which can carry up to M kilos. We have N items where each item has a cost and has a weight. We need to fill our bag in a way that we can have the maximum cost and the overall weight must not exceed M.
Just like in Knapsack with 1 parameter where we kept an array of trues and falses we will keep an array but this time an array of integers not booleans. Suppose the name of that array is A. The value of A[K] shows the maximum cost of the items which have a weigh K together.
Here is a pseudocode
Suppose we have 2 arrays
COST[N]
WEIGHT[N]
and our array of answers A.
for(i=1;i<=N;i++)
for(j=m;j>0;j++) //we start from the end because in this task the number of items of each type is 1 , if there were infinite items we were going to start form the beginning
{
if( j+WEIGHT[i] <=m //checking if the combination is possible AKA smaller than M// and A[j+WEIGHT[i]]<A[J]+COST[I] // If the new combination is better than the one previously collected//)
A[j+WIEGHT[i]]=A[k]+COST[i]; ///update the new combination
}
The problem is as follows
We have a bag which can carry up to M kilos. We have N items where each item has a cost and has a weight. We need to fill our bag in a way that we can have the maximum cost and the overall weight must not exceed M.
Just like in Knapsack with 1 parameter where we kept an array of trues and falses we will keep an array but this time an array of integers not booleans. Suppose the name of that array is A. The value of A[K] shows the maximum cost of the items which have a weigh K together.
Here is a pseudocode
Suppose we have 2 arrays
COST[N]
WEIGHT[N]
and our array of answers A.
for(i=1;i<=N;i++)
for(j=m;j>0;j++) //we start from the end because in this task the number of items of each type is 1 , if there were infinite items we were going to start form the beginning
{
if( j+WEIGHT[i] <=m //checking if the combination is possible AKA smaller than M// and A[j+WEIGHT[i]]<A[J]+COST[I] // If the new combination is better than the one previously collected//)
A[j+WIEGHT[i]]=A[k]+COST[i]; ///update the new combination
}
so many errors in explanations you wrote "in this task no. of items is 1" ? srsly dude? then for what the N is for?
ReplyDeleteHi. Thanks for your comment I fixed it and some other issues with the phrase "the number of items is 1" I meant that we have one of each type. sorry for misunderstanding :)
DeleteHi David! I love this blog. It's really helpful. I am currently running into a
Deleteproblem while submitting the solution to this problem on spoj. I downloaded your source code and ran it for a few test cases and found that the answers were similar to that of mine. I have tried to use the greedy approach. Here is my source code. Please help.
#include
using namespace std;
struct coin
{
float v,w,r;
};
void mergesort(coin a[],int start,int end)
{
int i=start,j=(start+end)/2+1;
if(start>t;
while(t--)
{
cin>>e>>f;
cin>>n;
coin c[n];
for(i=0;i>c[i].v>>c[i].w;
c[i].r=c[i].v/c[i].w;
}
mergesort(c,0,n-1);
int total=0,index=0,value=0;
while(true)
{
if(index==n-1&&c[index].w>f-e-total)
{
cout<<"This is impossible.\n";
break;
}
int mult=(int)(f-e-total)/c[index].w;
value+=c[index].v*mult;
total+=c[index++].w*mult;
if(total==f-e)
{
cout<<"The minimum amount of
money in the piggy-bank is "<>t;
}
Also please tell me if the greedy approach can be applied to this problem.
Thanks in advance.