0/1 Knapsack

Given N items and a knapsack with capacity V, each item can only be selected once. Item i has volume v[i] and value w[i]. Determine which items to select to maximize total value without exceeding the knapsack's volume.

Constraints:

• 0 < N, V ≤ 1000
• 0 < v[i], w[i] ≤ 1000

Time Complexity: O(N × V)

int n, m;
int f[100010], w[100010], v[100010];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    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];
    return 0;
}

To optimize space complexity, use a rolling array instead of a 2D aray to avoid memory limit exceeded errors. Since only the previous state affects the current one, we eliminate the first dimension and update the array from right to left to prevent using updated values in the same iteration.

The recurrence relation is:

f[j] = max(f[j], f[j - v[i]] + w[i])

Complete Knapsack

Each item can be selected multiple times. The goal remains to maximize value within volume constraints.

Time Complexity: O(N × V)

int n, m;
int v[100010], w[100010], f[100010];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    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];
    return 0;
}

Multiple Knapsack (Naive Approach)

Each item type has a limited quantity s[i]. Transform into 0/1 knapsack problem.

Time Complexity: O(N × V × S)

int n, m;
int f[100010], w[100010], v[100010], s[100010];

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

Binary Optimization for Multiple Knapsack

Split each item into log(s[i]) parts to reduce time complexity to O(N × V × log(S)).

int n, m;
int f[100010];
int ww[100010], vv[100010];

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

Monotonic Queue Optimization for Multiple Knapsack

Divide the knapsack capacity based on volume remainder to achieve O(N × V) complexity.

int n, m;
int f[200010], g[200010], q[200010];

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        memcpy(g, f, sizeof(f));
        int v, w, s;
        cin >> v >> w >> s;
        
        for (int j = 0; j < v; j++) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) hh++;
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                while (hh <= tt && g[k] >= g[q[tt]] + (k - q[tt]) / v * w) tt--;
                q[++tt] = k;
            }
        }
    }
    
    cout << f[m];
    return 0;
}

Grouped Knaspack

Items are grouped, and exactly one item from each group can be selected.

Time Complexity: O(N × V × S)

int n, m;
int f[10010];
int v[10010][10010], w[10010][10010], s[10010];

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

Mixed Knapsack

Combines 0/1, complete, and multiple knapsack types.

int n, m;
int f[100010];

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

Two-Dimensional Knapsack

Each item has two resource requirements (volume and weight).

int n, V, M;
int f[10010][10010];

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

Counting Optimal Solutions

Count how many ways to achieve maximum value in 0/1 knapsack.

int n, m;
int f[100010], g[100010];
const int MOD = 1000000007;

int main() {
    cin >> n >> m;
    
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    g[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        
        for (int j = m; j >= v; j--) {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if (maxv == f[j]) cnt = (cnt + g[j]) % MOD;
            if (maxv == f[j - v] + w) cnt = (cnt + g[j - v]) % MOD;
            g[j] = cnt;
            f[j] = maxv;
        }
    }
    
    int res = 0;
    for (int i = 0; i <= m; i++) {
        res = max(res, f[i]);
    }
    
    int cnt = 0;
    for (int i = 0; i <= m; i++) {
        if (res == f[i]) {
            cnt = (cnt + g[i]) % MOD;
        }
    }
    
    cout << cnt;
    return 0;
}

Finding Actual Solution

Reconstruct the optimal solution with lexicographically smallest item sequence.

int n, m;
int f[10010][10010], w[10010], v[10010];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    for (int i = n; i >= 1; 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]);
            }
        }
    }
    
    int j = m;
    for (int i = 1; i <= n; i++) {
        if (v[i] <= j && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    }
    
    return 0;
}

Dependency-Based Knapsack

Items have parent-child relationships. A child item requires its parent to be selected.

int n, m;
int f[1010][1010], w[1010], v[1010];
int e[1010], ne[1010], h[1010], idx = 0;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int child = e[i];
        dfs(child);
        
        for (int j = m - v[u]; j >= 0; j--) {
            for (int k = 0; k <= j; k++) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[child][k]);
            }
        }
    }
    
    for (int i = m; i >= v[u]; i--) {
        f[u][i] = f[u][i - v[u]] + w[u];
    }
    
    for (int i = 0; i < v[u]; i++) {
        f[u][i] = 0;
    }
}

int main() {
    cin >> n >> m;
    
    memset(h, -1, sizeof(h));
    
    int root;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }
    
    dfs(root);
    
    cout << f[root][m];
    return 0;
}