Fractional and Discrete knapsack problem

here is the program for fractional and discrete knapsack problem.

// knapsack.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

void FractionalKnapsack();

void DiscreteKnapsack();

void RandomInit();

void RandomizedQuickSort(int i, int j);

int RandomPartition(int i, int j);

int Random(int i, int j);

int size;

int Weight[100];

int Profit[100];

float ProfitWeightRatio[100];

int NumItems;

int Permute[100],per=0;

int _tmain(int argc, _TCHAR* argv[])

{

char ch;

printf("Enter the size of the Knapsack\n");

scanf("%d",&size);

printf("Enter the number of items to be put into knapsack\n");

scanf("%d",&NumItems);

fflush(stdin);

printf("Enter the weight of each item\n");

for(int i=0;i

scanf("%d",&Weight[i]);

fflush(stdin);

printf("Enter the profits of each Item\n");

for(int i=0;i

scanf("%d",&Profit[i]);

fflush(stdin);

printf("Are you looking for Fractional Knapsack problem

....If so press character F\n");

printf("Are you looking for Discrete Knapsack problem

... If so press Character D\n");

scanf("%c",&ch);

if (ch == 'F' || ch == 'f')

FractionalKnapsack();

else if (ch == 'D' || ch == 'd')

DiscreteKnapsack();

else

{

printf("You have entered wrong

knapsack problem identifier\n");

exit(0);

}

fflush(stdin);

printf("Finished\n");

scanf("%c",&ch);

return 0;

}

void FractionalKnapsack()

{

//calculate profit weight ratio for each and every item.

for(int i=0;i

{

ProfitWeightRatio[i] = ((float) Profit[i])/Weight[i];

Permute[i] = i;

}

RandomInit();

//Sort the ProfitWeightRatio array and also

update the order of items in permute array,

Weight array,Profit array after the sor.

RandomizedQuickSort(0,NumItems-1);

//After sorting it is just that inserting all the elements

until knapsack becomes full.

//Note that as this is fractional knapsack problem a

fraction of last item is inserted.

printf("After sort here are the values of various arrays\n");

printf("Weight Array ");

for(int i=0;i

printf("%d ",Weight[i]);

printf("\nProfit Array ");

for(int i=0;i

printf("%d ",Profit[i]);

printf("\nProfitWeightRatio Array");

for(int i=0;i

printf("%f ",ProfitWeightRatio[i]);

printf("\nPermute Array ");

for(int i=0;i

printf("%d ",Permute[i]);

int room = size;

printf("Items used to fill the knapsack are\n");

float profit=0,fraction=0;

int k=0,Item=0;

while(room &&

k<>

{

Item = Permute[k];

if(room > Weight[Item])

{

room = room - Weight[Item];

profit = profit + Profit[Item];

printf("Item: %d ",Item);

}

else

{

fraction = (float) room/ Weight[Item];

profit = profit + fraction * Profit[Item];

printf("Fractional Item: %d\n",Item);

room=0;

}

k++;

}

}

void RandomInit()

{

time_t sec;

time(&sec);

srand( (unsigned int) sec);

}

void RandomizedQuickSort(int i,int j)

{

int l =0;

if(i

{

l = RandomPartition(i,j);

RandomizedQuickSort(i,l-1);

RandomizedQuickSort(l+1,j);

}

}

int RandomPartition(int i, int j)

{

int l_rand = 0;

float swap_ele = 0;

int swap_permut=0;

l_rand = Random(i,j);

//swap the first element and l_rand element

in the ProfitWeightRatio error.

swap_ele = ProfitWeightRatio[i];

swap_permut = Permute[i];

ProfitWeightRatio[i] = ProfitWeightRatio[l_rand];

Permute[i] = Permute[l_rand];

ProfitWeightRatio[l_rand] = swap_ele;

Permute[l_rand] = swap_permut;

float pivot = ProfitWeightRatio[i];

int l=i+1;

int m=j;

do

{

while(ProfitWeightRatio[l] >= pivot)

l++;

while(ProfitWeightRatio[m] <>

m--;

if(l

{

swap_ele = ProfitWeightRatio[l];

swap_permut = Permute[l];

ProfitWeightRatio[l] = ProfitWeightRatio[m];

Permute[l] = Permute[m];

ProfitWeightRatio[m] = swap_ele;

Permute[m] = swap_permut;

}

}while(l

ProfitWeightRatio[i] = ProfitWeightRatio[m];

swap_permut=Permute[m];

Permute[m] = Permute[i];

Permute[i] = swap_permut;

ProfitWeightRatio[m] = pivot;

return m;

}

int Random(int i, int j)

{

return ((rand() % (j-i+1)) + i);

}

int knapsack(int size, int index);

void DiscreteKnapsack()

{

int max_profit=0;

max_profit = knapsack(size,0);

printf("Discrete Knapsack maximum profit %d", max_profit);

printf("Elements covered in discrete knapsack maximum profit is \n");

//for(int i=0;i

//printf("%d ",Permute[i]);

printf("\n");

}

int knapsack(int size, int index)

{

int p=0,l=0;

if(index >= NumItems ||

size <= 0)

return 0;

//select first

p = knapsack(size,index+1);

if(size >= Weight[index])

l = Profit[index] + knapsack(size-Weight[index],index+1);

if (p >= l)

{

return p;

}

else

{

//Permute[per++] = index;

return l;

}

}