Skip to main content

0/1 knapsack problem using Dynamic programming in C 

#include< stdio.h >
#include< conio.h >
#define MAX 20
void knapsackDP(int,int);
int max(int,int);
void backtracking();
int weight[MAX],value[MAX],W,no,*x;
int v[MAX][MAX];


void main()
{
 int i,j;
 clrscr();
 printf("\n Enter number of Object you want:");
 scanf("%d",&no);
 printf("\n Enter weight and values in ascending order of vales");;
 for(i=1;i<=no;i++)
 {
  printf("\n Enter Weight and Value for Object %d:",i);
  scanf("%d %d",&weight[i],&value[i]);
 }
 printf("\n Enter knapsack Capacity:");
 scanf("%d",&W);

 knapsackDP(no,W);
 backtracking();
getch();
}

void knapsackDP(int no,int W)
{
 int i,j;

 for(i=0;i<= W ;i++)
  v[0][i]=0;

 for(i=0;i<= no;i++)
  v[i][0]=0;

 for(i=1;i<= no;i++)
 {
  for(j=1;j<= W;j++)
  {
   if((j-weight[i])< 0)
    v[i][j]=v[i-1][j];
   else
    v[i][j]=max(v[i-1][j],v[i-1][j-weight[i]]+value[i]);
  }
 }
 printf("\n \t      ");
 for(i=0;i<= W;i++)
  printf("%2d  ",i);

 printf("\n-----------------------------------------------------------------------------");

 for(i=0;i<=no;i++)
 {
  printf("\n w%d=%2d v%d=%2d |",i,weight[i],i,value[i]);
  for(j=0;j<= W;j++)
   printf("%2d  ",v[i][j]);

 }
 printf("\n-----------------------------------------------------------------------------");
 printf("\n Maximum value carry by knapsack is:%2d",v[no][W]);
 printf("\n-----------------------------------------------------------------------------");
}

int max(int a,int b)
{
 return (a >b)?a:b;
}

void backtracking()
{

 int j1,i;
 j1=W;
 printf("\nIncluded Object \t weight \t value");
 printf("\n-----------------------------------------------------------------------------");
 for(i=no;i >=0;i--)
 {

  if(v[i][j1]!=v[i-1][j1] && (v[i][j1]==v[i-1][j1-weight[i]]+value[i]))
  {
   printf("\n%2d \t\t\t  %2d   \t\t %2d",i,weight[i],value[i]);
   j1=j1-weight[i];
  }

 }


}

OUTPUT

 Enter number of Object you want:5

 Enter weight and values in ascending order of values

 Enter Weight and Value for Object 1:1 1

 Enter Weight and Value for Object 2:2 6

 Enter Weight and Value for Object 3:5 18

 Enter Weight and Value for Object 4:6 22

 Enter Weight and Value for Object 5:7 28

Enter knapsack Capacity:11

                0   1   2   3   4    5    6    7    8    9   10  11
--------------------------------------------------------------------------
 w0= 0 v0= 0  | 0   0   0   0   0    0    0    0   0    0    0    0
 w1= 1 v1= 1  | 0   1   1   1   1    1    1    1   1    1    1    1
 w2= 2 v2= 6  | 0   1   6   7   7    7    7    7   7    7    7    7
 w3= 5 v3=18  | 0   1   6   7   7   18   19   24  25   25   25   25
 w4= 6 v4=22  | 0   1   6   7   7   18   22   24  28   29   29   40
 w5= 7 v5=28  | 0   1   6   7   7   18   22   28  29   34   35   40
--------------------------------------------------------------------------
 Maximum value carry by knapsack is:40
--------------------------------------------------------------------------
Included Object          weight          value
--------------------------------------------------------------------------
 4                           6              22
 3                           5              18
Labels:

Comments

Post a Comment

Popular posts from this blog

MVT (Multiprogramming Variable Task) in C Programming

#include< stdio.h> #include< conio.h> void main() { int i,os_m,nPage,total,pg[25]; clrscr(); printf("\nEnter total memory size:"); scanf("%d",&total); printf("\nEnter memory for OS:"); scanf("%d",&os_m); printf("\nEnter no. of pages:"); scanf("%d",&nPage); for(i=0;i< nPage;i++) { printf("Enter size of page[%d]:",i+1); scanf("%d",&pg[i]); } total=total-os_m; for(i=0;i< nPage;i++) { if(total>=pg[i]) { printf("\n Allocate page %d",i+1); total=total-pg[i]; } else printf("\n page %d is not allocated due to insufficient memory.",i+1); } printf("\n External Fragmentation is:%d",total); getch(); } OUTPUT Enter total memory size:1024 Enter memory for OS:256 Enter no. of pages:4 Enter size of page[1]:128 Enter size of page[2]:512 Enter size of page[3]:64 Enter size of page[4]:512 Allocate page 1 Al
7 comments
Read more

implement Rail fence cipher in Java

// File Name: RailFence.java import java.util.*; class RailFenceBasic{ int depth; String Encryption(String plainText,int depth)throws Exception { int r=depth,len=plainText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String cipherText=""; for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { if(k!=len) mat[j][i]=plainText.charAt(k++); else mat[j][i]='X'; } } for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { cipherText+=mat[i][j]; } } return cipherText; } String Decryption(String cipherText,int depth)throws Exception { int r=depth,len=cipherText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String plainText=""; for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { mat[i][j]=cipherText.charAt(k++); } } for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { plainText+=mat[j][i]; } }
Post a Comment
Read more

Deadlock Prevention using Banker’s Algorithm in C Programming

#include< stdio.h> #include< conio.h> void main() { int allocated[15][15],max[15][15],need[15][15],avail[15],tres[15],work[15],flag[15]; int pno,rno,i,j,prc,count,t,total; count=0; clrscr(); printf("\n Enter number of process:"); scanf("%d",&pno); printf("\n Enter number of resources:"); scanf("%d",&rno); for(i=1;i< =pno;i++) { flag[i]=0; } printf("\n Enter total numbers of each resources:"); for(i=1;i<= rno;i++) scanf("%d",&tres[i]); printf("\n Enter Max resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&max[i][j]); } printf("\n Enter allocated resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&allocated[i][j]); } printf("\n avai
Post a Comment
Read more