[go: up one dir, main page]
Scribd
Upload
31 views4 pages

Experiment4 AA

This document describes implementing a 0-1 knapsack problem using dynamic programming. It provides the theory behind 0-1 knapsack and explains how to represent the problem as a table to store optimal solutions in a bottom-up manner. Source code in C is included to write a program that takes item weights and profits as input and outputs the most valuable combination of items fitting within a capacity.

Uploaded by

Tanishka Mayekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views4 pages

Experiment4 AA

This document describes implementing a 0-1 knapsack problem using dynamic programming. It provides the theory behind 0-1 knapsack and explains how to represent the problem as a table to store optimal solutions in a bottom-up manner. Source code in C is included to write a program that takes item weights and profits as input and outputs the most valuable combination of items fitting within a capacity.

Uploaded by

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

Mahavir Education Trust's

SHAH & ANCHOR KUTCHHI ENGINEERING COLLEGE


Chembur, Mumbai - 400 088
UG Program in Electronics & Computer Science

Experiment No. 4

Aim: Implementation of a program for Knapsack problem.


Required Software/ Software Tool
- Windows Operating System
-C/C++

Theory:
In 0-1 Knapsack, items cannot be broken which means the thief should take the
item as a whole or should leave it. This is reason behind calling it as 0-1 Knapsack.
Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or 1, where other
constraints remain the same.0-1 Knapsack cannot be solved by Greedy approach.
A greedy approach does not ensure an optimal solution. In many instances, Greedy
approach may give an optimal solution. To solve 0-1 Knapsack, Dynamic
Programming approach is required.
Problem Statement
A thief is robbing a store and can carry a maximal weight of W into his knapsack.
There are n items and weight of ith item is wi and the profit of selecting this item
is pi. What items should the thieftake?

Dynamic-Programming Approach
Let ibe the highest-numbered item in an optimal solution S for W dollars. Then S'
= S - {i} is an optimal solution for W - wi dollars and the value to the solution S is
Vi plus the value of the sub- problem.

We can express this fact in the following formula: define c[i, w] to be the solution for
items 1,2,
… ,i and the maximum weight w.

The algorithm takes the following inputs

The maximum weight W

The number of items n

The two sequences v = <v1, v2, …, vn> and w = <w1, w2, …, wn>

Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
fori = 1 to n do
c[i, 0] = 0
for w = 1 to W do
ifwi ≤ w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
Mahavir Education Trust's
SHAH & ANCHOR KUTCHHI ENGINEERING COLLEGE
Chembur, Mumbai - 400 088
UG Program in Electronics & Computer Science

else c[i, w] = c[i-1, w]


else
c[i, w] = c[i-1, w]

The set of items to take can be deduced from the table, starting at c[n, w]and tracing
backwards where the optimal values came from.

If c[i, w] = c[i-1, w], then item i is not part of the solution, and we continue
tracing with c[i-1, w]. Otherwise, item i is part of the solution, and we continue
tracing with c[i-1, w-W].
Analysis
This algorithm takes θ(n, w) times as table c has (n + 1).(w + 1) entries, where
each entry requires θ(1) time to compute.

Implementing the Solution Writing Source Code:


//Tanishka Mayekar for(j=0;j<=cap;j++)
#include<stdio.h> if((i==0)||(j==0))
int w[10],p[10],v[10][10],n,i,j,cap; v[i][j]=0;
int x[10]={0}; else
int max(int i,int j){ v[i][j]=-1;
return ((i>j)?i:j); profit=knap(n,cap);
} i=n;
int knap(int i,int j){ j=cap;
int value; while(j!=0&&i!=0){
if(v[i][j]<0){ if(v[i][j]!=v[i-1][j]){
if(j<w[i]) x[i]=1;
value=knap(i-1,j); j=j-w[i];
else i--;
value=max(knap(i-1,j),p[i]+knap(i-1,j- }
w[i])); else
v[i][j]=value; i--;
} }
return(v[i][j]); printf("object included are \n ");
} printf("Sl.no\tweight\tprofit\n");
int main(){ for(i=1;i<=n;i++)
int profit,count=0; if(x[i])
printf("\nEnter the number of objects "); printf("%d\t%d\t%d\n",++count,w[i],p[i]);
scanf("%d",&n); printf("Total profit = %d\n",profit);
printf("Enter the profit and weights of the }
elements \n ");
for(i=1;i<=n;i++){
printf("\nEnter profit and weight For object
no %d :",i);
scanf("%d%d",&p[i],&w[i]);
}
printf("\nEnter the capacity ");
scanf("%d",&cap);
for(i=0;i<=n;i++)
Mahavir Education Trust's
SHAH & ANCHOR KUTCHHI ENGINEERING COLLEGE
Chembur, Mumbai - 400 088
UG Program in Electronics & Computer Science

Input and Output


Mahavir Education Trust's
SHAH & ANCHOR KUTCHHI ENGINEERING COLLEGE
Chembur, Mumbai - 400 088
UG Program in Electronics & Computer Science

Conclusion:
In this experiment we have implemented Knapsack problem.

You might also like