Skip to main content

Dynamic Programming - 0/1 Knapsack Problem

➤ Greedy algo does not give optimal solution everytime.
     Exa. Consider  n=3 and Capacity W=30
              w={20,10,5}
              p={180,80,50}
              p/w={9,8,10}
              greedy solution={1,0,1} ➝ profit =180+50=230
              optimal solution={1,1,0} ➝ profit=180+80=260

Algo :- 
  • w[i] gives weight of ith item.
  • p[i] gives value(profit) of ith item.
  • sol[i][j] gives the maximum profit for i items and j capacity(sub problem)
Use Desktop Version Of This Site For Better View.

for(j=0 to m) ➝ No Capicity No Packets
     sol[0][j]=0

for(i=0 to m) ➝ No Items
     sol[i][0]=0

for(i=1 to n) 
     for(j=1 to m)
          if(w[i] > j)                     ➝ ith item not selected because weight of the 
              sol[i][j]=sol[i-1][j]         ith item  is more than available capacity
          else                               ➝ select ith item if total profit with ith item is 
                                                     more  than profit without ith item
              sol[i][j]=max{sol[i-1][j] , sol[i-1][j-w[i]]+p[i]}

Programme :- 

Download the programme

#include<stdio.h>
int findmax(int x,int y)
{
    int max=x;
    if(y>max)
    {
        max=y;
    }
    return max;
}
main()
{
    int n,i,j;
 printf("ENTER THE TOTAL ITEMS : ");
 scanf("%d",&n);
 int w[n],p[n],W;
 for(i=0;i<n;i++)
 {
  printf("ITEM NO.%d\nWEIGHT : ",(i+1));
  scanf("%d",&w[i]);
  printf("VALUE : ");
  scanf("%d",&p[i]);
 }
 printf("ENTER THE MAXIMUM CAPACITY OF KNAPSACK : ");
 scanf("%d",&W);

    int sol[n+1][W+1];
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if (i==0 || j==0)
            {
                sol[i][j]=0;
            }
            else if(w[i-1]>j)
            {
                sol[i][j]=sol[i-1][j];
            }
            else
            {
                sol[i][j]=findmax(sol[i-1][j],sol[i-1][j-w[i-1]]+p[i-1]);
            }
           // printf("sol[%d][%d] : %d\t",i,j,sol[i][j]);
        }
        //printf("\n");
    }
    i=n;
    j=W;
    while(i>0 && j>0)
    {
        if(sol[i][j]>sol[i-1][j])
        {
            printf("ITEM[%d] IS SELECTED.\n",i);
            j=j-w[i-1];

        }
        i--;
    }
    printf("PROFIT : %d",sol[n][W]);
}
Analysis : 
  • Algo takes O(n*W) time as the size of sol array is n*w where n is the number of items and W is the capacity of knapsack.
  • It is not polynomial time algorithm.
  • It is Pseudo-polynomial algorithm.
    • Pseudo-polynomial algorithm : - An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo-polynomial algorithm. 

Comments

Popular Posts

Dijkstra's algorithm

Djikstra's algorithm   solves the problem of finding the shortest path from a point in a graph (the  source ) to a destination. It turns out that one can find the shortest paths from a given source to  all  points in a graph in the same time, hence this problem is sometimes called the  single-source shortest paths  problem. This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G = (V,E) where V is a set of vertices and E is a set of edges. Dijkstra's algorithm keeps two sets of vertices: S    the set of vertices whose shortest paths from the source have already been determined  and V-    S :   the remaining v...

Balanced Brackets

Balanced Brackets :- A bracket is considered to be any one of the following characters:  ( ,  ) ,  { ,  } ,  [ , or  ] . Two brackets are considered to be a  matched pair  if the an opening bracket (i.e.,  ( ,  [ , or  { ) occurs to the left of a closing bracket (i.e.,  ) ,  ] , or  } )  of the exact same type . There are three types of matched pairs of brackets:  [] ,  {} , and  () . A matching pair of brackets is  not balanced  if the set of brackets it encloses are not matched. For example,  {[(])} is not balanced because the contents in between  {  and  }  are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket,  ( , and the pair of parentheses encloses a single, unbalanced closing square bracket,  ] . By this logic, we say a sequence of brackets is considered to be  balanced  if the follow...

Kruskal’s Minimum Spanning Tree Algorithm & Programme

PROBLEM :                  Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. To understand Kruskal's algorithm let us consider the following example − Step 1 - Remove all loops and Parallel Edges Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and ove all others. Step 2 - Arrange all edges in their increasing order of weight The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost). Step 3 - Add the edge which has the least weightage Now we start adding edges to the graph beginning from the one which has the least weight. Th...