Write a Program to implement a backtracking algorithm for knapsack problem?

Answer 1

#include<stdio.h>

#include<conio.h>

#include<iostream.h>

#include "knapheap.h"

struct knapshap *c;

float x[100];

void knapshap(struct knapshap *c,int m,int n)

{

int i;

for(i=0;i<n;i++)

{

x[i]=0.0;

}

i=0;

while(c[i].totwt<=m &&i<n)

{

x[i]=1.0;

m=m-c[i].totwt;

i++;

}

if(i<=n)

{

x[i]=(m/c[i].totwt);

m=0;

}

cout<<"\n the soln. vector=";

for(int j=0;j<n;j++)

cout<<"\n"<<x[j];

}

void main()

{

clrscr();

int p[100],w[100],n,i,m=0;

cout<<"enter the size of the vector";

cin>>n;

cout<<"enter the price of each item";

for(i=1;i<=n;i++)

cin>>p[i];

cout<<"enter the wt of each item";

for(i=1;i<=n;i++)

{

cin>>w[i];

}

cout<<"enter maxm wt of knapshap";

cin>>m;

for(i=1;i<=n;i++)

{

a[i].pcwt=p[i]/w[i];

a[i].totwt=w[i];

}

build_max_heap(a,n);

c=heap_sort(a);

cout<<"\n sorted items \n";

for(i=0;i<n;i++)

{

cout<<" pc="<<c[i].pcwt<<" wt="<<c[i].totwt<<"\n";

}

knapshap(c,m,n);

getch();

}