Dynamic Programming VTU BCSL40A

0/1 Knapsack Problem

The 0/1 Knapsack problem uses dynamic programming to find the maximum profit by selecting items with given weights and values without exceeding the knapsack capacity.

Time Complexity

O(nW)

Space Complexity

O(nW)

Paradigm

Dynamic Programming

Introduction

The 0/1 Knapsack Problem is a classic optimization problem solved using Dynamic Programming. Given n items each with a weight and a profit value, and a knapsack of capacity W, the goal is to determine which items to include to maximize the total profit without exceeding the capacity. Each item can either be included (1) or excluded (0) — hence the name '0/1 Knapsack'.

Problem Statement

Given n items with weights w[1..n] and values v[1..n], and a knapsack capacity W, find the maximum value subset of items such that the sum of weights ≤ W. Each item is either taken (1) or left (0).

Real World Applications

→ Resource allocation in project management
→ Portfolio optimization in finance
→ Cargo loading for ships/planes
→ Memory management in operating systems
→ Cryptography and subset-sum based problems

Algorithm Explanation

Build a 2D table v[i][j] where v[i][j] = maximum profit using items 1..i with capacity j. Base case: v[0][j] = 0 (no items) and v[i][0] = 0 (no capacity). Recurrence: if wt[i] > j, v[i][j] = v[i-1][j] (can't include item i); else v[i][j] = max(v[i-1][j], v[i-1][j-wt[i]] + val[i]). The answer is v[n][W]. Backtrack to find selected items.

Step-by-Step Procedure

1 Read n (number of items), val[1..n] (profits), wt[1..n] (weights), and c (capacity).
2 Build DP table v[n+1][c+1], initialized to 0.
3 For each item i from 1 to n and each capacity j from 0 to c:
4 If wt[i] > j: v[i][j] = v[i-1][j] (item too heavy)
5 Else: v[i][j] = max(v[i-1][j], v[i-1][j-wt[i]] + val[i])
6 Answer = v[n][c]. Backtrack: if v[n][c] ≠ v[n-1][c], item n is selected.
7 Print selected items and maximum profit.

Complete C Program

o_1knapsack.c

View on GitHub ↗

#include<stdio.h>
#include<stdlib.h>

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

int val[20], wt[20], v[20][20], n, c;

int knap() {
    int i, j;
    for(i = 0; i <= n; i++) {
        for(j = 0; j <= c; j++) {
            if(i == 0 || j == 0)
                v[i][j] = 0;
            else if(wt[i] > j)
                v[i][j] = v[i-1][j];
            else
                v[i][j] = my_max(v[i-1][j], v[i-1][j-wt[i]] + val[i]);
        }
    }
    return v[n][c];
}

int main() {
    int i, j, opt;
    printf("Enter the Number of Items: ");
    scanf("%d", &n);
    printf("Enter the Values (profits): ");
    for(i = 1; i <= n; i++) scanf("%d", &val[i]);
    printf("Enter the Weights: ");
    for(i = 1; i <= n; i++) scanf("%d", &wt[i]);
    printf("Enter the Knapsack Capacity: ");
    scanf("%d", &c);
    opt = knap();
    printf("\nDP Table:\n");
    printf("Capacity:");
    for(j = 0; j <= c; j++) printf("%4d", j);
    printf("\n");
    for(i = 0; i <= n; i++) {
        printf("Item--%2d:", i);
        for(j = 0; j <= c; j++) printf("%4d", v[i][j]);
        printf("\n");
    }
    printf("\nMaximum Profit: %d\n", opt);
    printf("Selected Items: ");
    while(n > 0) {
        if(v[n][c] != v[n-1][c]) {
            printf("%d ", n);
            c -= wt[n];
        }
        n--;
    }
    printf("\n");
    return 0;
}

Sample Input & Output

Sample Input

Expected Output

Maximum Profit: 8
Selected Items: 4 2

Dry Run / Trace

n=3, values=[1,2,5], weights=[2,3,4], capacity=5.
v[1][j]: 0,0,1,1,1,1
v[2][j]: 0,0,1,2,2,3
v[3][j]: 0,0,1,2,5,5
Maximum profit = v[3][5] = 5. Backtrack: item 3 selected (c=5→1). Item 2 not selected. v[1][1]=0=v[0][1]=0.
Selected: item 3.

Advantages & Disadvantages

✓ Advantages

+ Guarantees the optimal solution
+ Solves the exact 0/1 constraint (no fractional items)
+ DP table helps trace back selected items
+ Works for any weight/value combination

✗ Disadvantages

− O(nW) time and space — can be large for high capacities
− Not suitable when capacity W is very large (pseudo-polynomial)
− Only handles integer weights in standard DP approach

Viva Questions & Answers

Q1. What is the difference between 0/1 Knapsack and Fractional Knapsack?

In 0/1 Knapsack, items are either taken or left (no splitting). In Fractional Knapsack, items can be split and fractions can be taken.

Q2. Why is 0/1 Knapsack solved with DP and not greedy?

Greedy (by value/weight ratio) doesn't always give optimal results for 0/1 Knapsack. DP explores all combinations systematically.

Q3. What is the recurrence relation for 0/1 Knapsack?

v[i][j] = max(v[i-1][j], v[i-1][j-w[i]] + val[i]) if w[i] ≤ j, else v[i][j] = v[i-1][j].

Q4. How do you find which items are selected after computing the DP table?

Start from v[n][W]. If v[n][W] ≠ v[n-1][W], item n is selected; reduce W by w[n]. Repeat for n-1, n-2, ...

Q5. What is the time complexity of 0/1 Knapsack?

O(nW) where n is the number of items and W is the knapsack capacity. Space is also O(nW) for the DP table.