![:)](./images/smilies/icon_smile.gif)
Keep posting emotional blind. You are really helpful.
![:D](./images/smilies/icon_biggrin.gif)
mukit.
Moderator: Board moderators
HI Every one.
I solve this problem with knapsack
but i want to make it faster can any one tell me how can i do this.
![]()
Code: Select all
# include <iostream>
//#include <fstream>
using namespace std;
int MAX( int X, int Y )
{
if ( X>Y )
return X;
else return Y;
}
int Knapsack(int WeightOfPerson,int WeightOfObiects[] ,int PriceOfobject[], int NumberOfObjects )
{
int KSTable[30][1000]={0};
for (int i=0; i<=WeightOfPerson ;i++)
for (int j=1; j<=NumberOfObjects ;j++)
{
if ( WeightOfObiects[j-1]> i)
KSTable[i][j]=KSTable[i][j-1];
else
{
KSTable[i][j]=MAX ( KSTable[i][j-1], KSTable[i-WeightOfObiects [j-1]][j-1]+PriceOfobject [j-1]);
}
}
return KSTable[WeightOfPerson][NumberOfObjects ];
}
//# define cin fin
int main()
{
/*ifstream fin;
fin.open("input.txt");*/
int NumberOfCases, NumberOfObjects,NumberOfPersons, MaxValueOfObjecs=0;
int PriceOfobject[1000]={0};
int WeightOfObiects[1000]={0};
int WeightOfPersons[100]={0};
cin >> NumberOfCases;
for (int MM=0; MM<NumberOfCases ;MM++)
{
cin >> NumberOfObjects;
for (int j=0; j<NumberOfObjects ;j++)
{
cin >> PriceOfobject[j];
cin >> WeightOfObiects[j];
}
cin>> NumberOfPersons ;
for (int j=0; j<NumberOfPersons ;j++)
{
cin >> WeightOfPersons[j];
}
//Sort
int key,i,key1;
for(int j=1;j<NumberOfObjects ;j++)
{
key=WeightOfObiects [j];
key1= PriceOfobject [j];
i=j-1;
while(WeightOfObiects [i]>key && i>=0)
{
WeightOfObiects [i+1]=WeightOfObiects [i];
PriceOfobject [i+1]=PriceOfobject[i];
i--;
}
WeightOfObiects [i+1]=key;
PriceOfobject [i+1]=key1;
}
for(int j=0;j<NumberOfPersons ;j++)
{
MaxValueOfObjecs+= Knapsack(WeightOfPersons[j],WeightOfObiects , PriceOfobject, NumberOfObjects);
}
cout<< MaxValueOfObjecs<<endl;
MaxValueOfObjecs=0;
}
return 0;
}
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int value[150],weight[150],C[50][50],N,W;
int knapsack(int N,int W){
int i,w,temp;
// memset(C,0,sizeof C);
for(i=1 ; i<=N ; i++) C[i][0]=0;
for(w=0 ; w<=W ; w++) C[0][w]=0;
for(i=0 ; i<=N ; i++)
for(w=1 ; w<=W ; w++){
if (weight[i] > w)
C[i][w] = C[i-1][w];
else
C[i][w] = max(C[i-1][w] , C[i-1][w-weight[i]]+value[i]);
}
temp=C[N][W];
// cout<<temp<<endl;
return temp;
}
int main(){
int TC,person;
// freopen("10130.txt","r",stdin);
while(scanf("%d",&TC)==1){
while(TC--){
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d %d",&value[i],&weight[i]);
}
scanf("%d",&person);
int total=0,sum;
for(int i=0;i<person;i++){
scanf("%d",&W);
sum=knapsack(N,W);
total = total + sum;
}
cout<<total<<endl;
}
}
return 0;
}