Scribd
Upload
12 views1 page

Knapsack

knapsack solutiion

Uploaded by

Purushothama Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
12 views1 page

Knapsack

knapsack solutiion

Uploaded by

Purushothama Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

#include<stdio.

h>
#include<stdlib.h>
#define MAX_ITEMS 100
#define MAX_WEIGHT 100

int max(int a,int b){


if(a>b){
return a;
}
return b;
}

void knapsack(int n,int W,int weights[],int values[]){


int dp[MAX_ITEMS+1][MAX_WEIGHT+1];
for(int i=0;i<=n;i++){
for(int w=0;w<=W;w++){
if(i==0 || w==0){
dp[i][w] =0;
}
else if(weights[i-1]<=w){
dp[i][w] = max(values[i-1]+dp[i-1][w-weights[i-
1]],dp[i-1][w]);
}
else{
dp[i][w] = dp[i-1][w];
}
}
}
printf("Maximn value : %d\n",dp[n][W]);
int w = W;
printf("selected items (weigfht value):");
for(int i = n;i> 0 && w >0;i--){
if(dp[i][w] != dp[i-1][w]){
printf("(%d %d)",weights[i-1],values[i-1]);
w -= weights[i-1];
}
}
printf("\n");

}
int main(){
int n,W;
printf("enter no of items:");
scanf("%d",&n);
printf("enter maximum knapsack weights:");
scanf("%d",&W);
int weights[n],values[n];
printf("enter weights and valuue of items:");

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

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

}
knapsack(n,W,weights,values);
return 0;
}
\

You might also like