Understanding Problem Types in Dynamic Programming

Dynamic programming problems often involve defining states and transitioning between them. Common types include:

• Knapsack Problems
• Linear DP
• Interval DP
• State Compression DP
• Tree DP
• Counting Problems
• Digit-based DP
• State Compression
• Memorized Search

Knapsack Problems

0/1 Knapsack (Each item can be chosen once)

In this classic problem, we have N items and a knapsack with capacity V. Each item has a weight and value. The goal is to maximize the total value without exceeding the capacity.

State Representation:

• f(i, j) represents the maximum value achievable by considering the first i items with a capacity of j
• The final answer is found in f(n, v)

State Transition:

f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])#### 2D Implementation

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for (int j = 0; j <= m; j++) f[0][j] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i-1][j];
            if (v[i] <= j) {
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}

1D Optimizaton

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for (int i = 0; i <= m; i++) f[i] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

Unbounded Knapsack (Each item can be chosen unlimited times)

The key difference from 0/1 knapsack is that we can take multiple copies of each item.

1D Optimized Implementation

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for (int i = 0; i <= m; i++) f[i] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

Multiples Knapsack (Each item has a limited number of copies)

This variant adds a quantity constraint to each item.

Binary Optimization Implementation

#include <bits/stdc++.h>
using namespace std;

const int N = 25000;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    int cnt = 0;
    int temp_n = n;
    
    while (temp_n--) {
        int a, b, S;
        cin >> a >> b >> S;
        int k = 1;
        while (k < S) {
            S -= k;
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            k *= 2;
        }
        if (S) {
            cnt++;
            v[cnt] = a * S;
            w[cnt] = b * S;
        }
    }
    
    n = cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

Grouped Knapsack (Selecting one item from each group)

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;
int v[N][N], w[N][N];
int s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i-1][j];
            for (int k = 0; k < s[i]; k++) {
                if (v[i][k] <= j) {
                    f[i][j] = max(f[i][j], f[i-1][j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}