AIM:
To solve 0/1 Knapsack problem using Dynamic Programming.
DESCRIPTION:
The Knapsack problem is probably one of the most interesting and most popular in computer science, especially when we talk about dynamic programming.The knapsack problem is a problem in combinatorial optimization. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Basic Algorithm:
Input:
a set of items with weights and values
output:
the greatest combined value of a subset
partition the set {1...n} into two sets A and B of approximately equal size
compute the weights and values of all subsets of each set
for each subset of A
find the subset of B of greatest value such that the combined weight is less than W
keep track of the greatest combined value seen so far
ALGORITHM:
Input:
Values (stored in array v or profit)
Weights (stored in array w or weight)
Number of distinct items (n)
Knapsack capacity (W)
for j from 0 to W do
m[0, j] = 0
end for
for i from 1 to n do
for j from 0 to W do
if w[i] <= j then
m[i, j] = max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] = m[i-1, j]
end if
end for
end for
CODE:
#include <iostream>
#include <cstdlib>
using namespace std;
const int MAX = 10;
inline int max(int a, int b);
void fnProfitTable(int w[MAX], int p[MAX], int n, int c, int t[MAX][MAX]);
void fnSelectItems(int n,int c, int t[MAX][MAX], int w[MAX], int l[MAX]);<\pre>
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/<\pre>
int main(void)
{
int i, j, totalProfit;
int weight[MAX];
int profit[MAX];
int capacity;
int num;
int loaded[MAX];
int table[MAX][MAX];
cout<<"Enter the maxium number of objects : ";
cin >> num;
cout << "Enter the weights : \n";
for (i=1; i<=num; i++)
{
cout << "\nWeight " << i << ": ";
cin >> weight[i];
}
cout << "\nEnter the profits : \n";
for (i=1; i<=num; i++)
{
cout << "\nProfit " << i << ": ";
cin >> profit[i];
}
cout << "\nEnter the maximum capacity : ";
cin >> capacity;
totalProfit = 0;
for( i=1; i<=num; i++)
loaded[i] = 0;
fnProfitTable(weight,profit,num,capacity,table);
fnSelectItems(num,capacity,table,weight,loaded);
cout << "Profit Matrix\n";
for (i=0; i<=num; i++)
{
for(j=0; j<=capacity; j++)
{
cout <<"\t"<<table[i][j];
}
cout << endl;
}
cout << "\nItem numbers which are loaded : \n{ ";
for (i=1; i<=num; i++)
{
if (loaded[i])
{
cout <<i << " ";
totalProfit += profit[i];
}
}
cout << "}" << endl;
cout << "\nTotal Profit : " << totalProfit << endl;
return 0;
}
inline int max(int a, int b)
{
return a>b ? a : b;
}
/******************************************************************************
*Function : fnProfitTable
*Description : Function to construct the profit table
*Input parameters:
* int w[MAX] - weight vector
* int p[MAX] - profit vector
* int n - no of items
* int c - knapsack capacity
* int t[MAX][MAX] - profit table
*RETURNS : no value
******************************************************************************/
void fnProfitTable(int w[MAX], int p[MAX], int n, int c, int t[MAX][MAX])
{
int i,j;
for (j=0; j<=c; j++)
t[0][j] = 0;
for (i=0; i<=n; i++)
t[i][0] = 0;
for (i=1; i<=n; i++)
{
for (j=1; j<=c; j++)
{
if (j-w[i] < 0)
t[i][j] = t[i-1][j];
else
t[i][j] = max( t[i-1][j], p[i] + t[i-1][j-w[i]]);
}
}
}
/******************************************************************************
*Function : fnSelectItems
*Description: Function to determine optimal subset that fits into the knapsack
*Input parameters:
* int n - no of items
* int c - knapsack capacity
* int t[MAX][MAX] - profit table
* int w[MAX] - weight vector
* int l[MAX] - bit vector representing the optimal subset
*RETURNS : no value
******************************************************************************/
void fnSelectItems(int n,int c, int t[MAX][MAX], int w[MAX], int l[MAX])
{
int i,j;
i = n;
j = c;
while (i >= 1 && j >= 1)
{
if (t[i][j] != t[i-1][j])
{
l[i] = 1;
j = j - w[i];
i--;
}
else
i--;
}
}
OUTPUT:
Enter the maxium number of objects : 4 Enter the weights :
Weight 1: 2
Weight 2: 1
Weight 3: 3
Weight 4: 2
Enter the profits :
Profit 1: 12
Profit 2: 10
Profit 3: 20
Profit 4: 15
Enter the maximum capacity : 5 Profit Matrix 0 0 0 0 0 0 0 0 12 12 12 12 0 10 12 22 22 22 0 10 12 22 30 32 0 10 15 25 30 37
Item numbers which are loaded : { 1 2 4 }
Total Profit : 37