0-1 Knapsack Problem using Dynamic Programming - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Design and Analysis of Algorithms Technology 0-1 Knapsack Problem using Dynamic Programming

    0-1 Knapsack Problem using Dynamic Programming

    Share This

    The 0/1 Knapsack Problem is a classic problem in combinatorial optimization. Given a set of items, each with a weight and a value, the goal is to determine the most valuable subset of items to include in a knapsack that has a fixed capacity. The catch is that you can either take an item or leave it (hence "0/1"), meaning you can't take a fraction of any item.


    Let i be the highest-numbered item in an optimal solution S for W pounds. Then S' = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.


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


    1
    2
    3
    4
    5
    0 if i = 0 or w = 0
    c[i,w] = c[i-1, w] if wi >= 0
    max [vi + c[i-1, w - wi], c[i - 1, w]} if i > 0 and w >= wi
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    This says that the value of the solution to i items either include ith item, in which case it is vi plus a subproblem solution for (i - 1) items and the weight excluding wi, or does not include ith item, in which case it is a subproblem's solution for (i - 1) items and the same weight. That is, if the thief picks item i, thief takes vi value, and thief can choose from items w - wi, and get c[i - 1, w - wi] additional value. On other hand, if thief decides not to take item i, thief can choose from item 1,2, ..., i-1 upto the weight limit w, and get c[i - 1, w] value. The better of these two choices should be made.


    The algorithm takes the maximum weight W as input, the number of items n, and the two sequences v = < v1, v2, ..., vn > and w = < w1, w2, ..., wn >. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 .. n, 0 .. w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.

    Algorithm: Dynamic-0-1-knapsack (v, w, n, W)
  
FOR w = 0 TO W
    DO  c[0, w] = 0
FOR i=1 to n
    DO c[i, 0] = 0
        FOR w=1 TO W
            DO IFf wi <= w
                THEN IF  vi + c[i-1, w-wi]
                    THEN c[i, w] = vi + c[i-1, w-wi]
                    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] item i is not part of the solution, and we are 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 dynamic-0-1-kanpsack algorithm takes Big-Theta(nw) times, broken up as follows: Big-Theta(nw) times to fill the c-table, which has (n +1).(w +1) entries, each requiring Big-Theta(1) time to compute. O(n) time to trace the solution, because the tracing process starts in row n of the table and moves up 1 row at each step.

    Dynamic 0/1-knapsack Implementation in C Language
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    #include <stdio.h>
    #include <stdlib.h>
    int larger(int a, int b) {
    return (a > b)? a : b;
    }
    // Returns the maximum value that can be put in a knapsack of capacity W
    int knapsack(int W, int wt[], int val[], int n)
    {
    int i, w;
    int **K;
    K = (int **) malloc((n+1)*sizeof(int *));
    for (i = 0; i <= n; i++)
    {
    K[i] = (int *)malloc((W+1)* sizeof(int));
    }
    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
    for (w = 0; w <= W; w++)
    {
    if (i==0 || w==0)
    K[i][w] = 0;
    else if (wt[i-1] <= w)
    K[i][w] = larger(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
    else
    K[i][w] = K[i-1][w];
    }
    }
    return K[n][W];
    }
    int main()
    {
    int *val;
    int *wt;
    int W;
    int n;
    printf("Enter the number of items:");
    scanf("%d", &n);
    val = (int *)malloc(n * sizeof(int));
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    Newer Article Sum of Sub-Sets Problem using Backtracking Older Article Selective Repeat ARQ using C Language
    By on
    Labels: ,
    Subscribe to: Post Comments (Atom)
    Comment Using!!

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    About BunksAllowed