0/1 Knapsack Model

Given a knapsack with capacity V and n items, each item has a value v and weight w. Each item can be taken at most once. Determine the maximum total value that can be placed in the knapsack.

There are two states for each item: take or not take, leading too 2^n possibilities.

Define state dp[i][j] as the maximum value achievable using the first i items with total weight j. We only care about the maximum value for the current weight.

Transition equation: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) If not taking the item, the maximum value is dp[i-1][j]. If taking it, the capacity reduces by w and value increases by v. Since i depends on i-1, initialize the dp array to 0 when j=0.

Example Problem:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_ITEMS = 105, MAX_CAPACITY = 1010;
int dp[MAX_ITEMS][MAX_CAPACITY];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int itemCount, capacity;
    cin >> itemCount >> capacity;

    for (int i = 1; i <= itemCount; ++i) {
        int weight, value;
        cin >> weight >> value;
        for (int j = 0; j <= capacity; ++j) {
            if (j >= weight) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[itemCount][capacity] << '\n';
    return 0;
}

0/1 Knapsack Optimization

Reduce the 2D array to 1D to save space and prevent memory limitssues. Time complexity remains the same with two loops. After converting to 1D, update from back to front to avoid using updated data for further updates.

State transition formula: dp[j] = max(dp[j], dp[j-w] + v)

Optimized Example:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_CAPACITY = 1010;
int dp[MAX_CAPACITY];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int itemCount, capacity;
    cin >> itemCount >> capacity;

    for (int i = 1; i <= itemCount; ++i) {
        int weight, value;
        cin >> weight >> value;
        for (int j = capacity; j >= weight; --j) {
            dp[j] = max(dp[j], dp[j-weight] + value);
        }
    }
    cout << dp[capacity] << '\n';
    return 0;
}

Example Problems

Knapsack with Magic

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_CAPACITY = 10005;
int dp[MAX_CAPACITY][2]; // 0: not using magic, 1: using magic

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int itemCount, capacity, magicCost;
    cin >> itemCount >> capacity >> magicCost;
    for (int i = 1; i <= itemCount; ++i) {
        int weight, value;
        cin >> weight >> value;
        for (int j = capacity; j >= 0; --j) {
            if (j >= weight) {
                dp[j][0] = max(dp[j][0], dp[j-weight][0] + value);
                dp[j][1] = max(dp[j][1], dp[j-weight][1] + value);
            }
            if (j >= weight + magicCost) {
                dp[j][1] = max(dp[j][1], dp[j-weight-magicCost][0] + 2 * value);
            }
        }
    }
    cout << max(dp[capacity][0], dp[capacity][1]) << '\n';
    return 0;
}

Course Selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_TIME = 1e5+10;

struct Course {
    int startTime;
    int endTime;
    int value;
};

int dp[MAX_TIME];
Course courses[MAX_TIME];

bool compare(Course a, Course b) {
    return a.endTime <= b.endTime;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int courseCount;
    cin >> courseCount;
    int maxEndTime = 0;
    for (int i = 1; i <= courseCount; ++i) {
        cin >> courses[i].startTime >> courses[i].endTime >> courses[i].value;
        maxEndTime = max(maxEndTime, courses[i].endTime);
    }
    sort(courses + 1, courses + courseCount + 1, compare);
    int maxValue = 0;
    for (int i = 1; i <= courseCount; ++i) {
        for (int j = maxEndTime; j >= courses[i].startTime; --j) {
            if (j <= courses[i].endTime) {
                dp[j] = max(dp[j], dp[j - courses[i].startTime] + courses[i].value);
            }
            maxValue = max(dp[j], maxValue);
        }
    }
    cout << maxValue << '\n';
    return 0;
}

Shopping Strategy

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[4100];
int itemValue[2100], itemCost[2100];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int itemCount, maxItems = 0;
    cin >> itemCount;
    for (int i = 1; i <= itemCount; ++i) {
        cin >> itemValue[i] >> itemCost[i];
        maxItems = max(maxItems, itemValue[i]);
        itemValue[i]++;
    }
    maxItems += itemCount;
    for (int i = 1; i <= maxItems; ++i) dp[i] = 1e18;
    for (int i = 1; i <= itemCount; ++i) {
        for (int j = maxItems; j >= itemValue[i]; --j) {
            dp[j] = min(dp[j], dp[j - itemValue[i]] + itemCost[i]);
        }
    }
    int minCost = 1e18;
    for (int i = itemCount; i <= maxItems; ++i) {
        minCost = min(minCost, dp[i]);
    }
    cout << minCost << '\n';
    return 0;
}

Lan's Secret Gift

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[1100];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int capacity, itemCount;
    cin >> capacity >> itemCount;
    while (itemCount--) {
        int weight;
        cin >> weight;
        for (int j = capacity; j >= weight; --j) {
            dp[j] = max(dp[j], dp[j - weight] + weight);
        }
    }
    cout << capacity - dp[capacity] << '\n';
    return 0;
}

Complete Knapsack Model

Also known as unbounded knapsack, where each item can be taken infinitely.

Define state dp[i] as the maximum value achievable with total weight i. Transition equation: dp[i] = max(dp[i], dp[i-w] + v). Unlike 0/1 knapsack, update from front to back because items can be taken multiple times.

Example:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_CAPACITY = 1e3+10;
int dp[MAX_CAPACITY];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int itemCount, capacity;
    cin >> itemCount >> capacity;
    for (int i = 1; i <= itemCount; ++i) {
        int weight, value;
        cin >> weight >> value;
        for (int j = weight; j <= capacity; ++j) {
            dp[j] = max(dp[j], dp[j - weight] + value);
        }
    }
    cout << dp[capacity] << '\n';
    return 0;
}

Two-Dimensional Cost Knapsack Model

Given a knapsack with capacity V and weight limit M, n items each with value v, volume w, and weight m. Each item can be taken at most once. Determine the maximum total value.

Extend the 0/1 knapsack to two dimensions. State dp[i][j] represents maximum value with volume i and weight j. Transition: dp[i][j] = max(dp[i][j], dp[i-v][j-m] + w). Time complexity O(n * V * M).

Example:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_VOLUME = 105, MAX_WEIGHT = 105;
int dp[MAX_VOLUME][MAX_WEIGHT];

signed main() {
    int itemCount, maxVolume, maxWeight;
    cin >> itemCount >> maxVolume >> maxWeight;
    for (int i = 1; i <= itemCount; ++i) {
        int volume, weight, value;
        cin >> volume >> weight >> value;
        for (int j = maxVolume; j >= volume; --j) {
            for (int k = maxWeight; k >= weight; --k) {
                dp[j][k] = max(dp[j][k], dp[j - volume][k - weight] + value);
            }
        }
    }
    cout << dp[maxVolume][maxWeight] << '\n';
    return 0;
}

Group Knapsack Model

Given a knapsack with capacity V and n groups of items. Each group has several items with value v and weight w. At most one item can be selected from each group. Determine the maximum total value.

State dp[i][j] represents maximum value using first i groups with total weight j. Transition: dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v). Before transition, copy dp[i][j] = dp[i-1][j].

Example:

#include <bits/stdc++.h>
using namespace std;
const int MAX_GROUPS = 1000, MAX_CAPACITY = 1000;
int dp[MAX_GROUPS][MAX_CAPACITY];

int main() {
    int groupCount, capacity;
    cin >> groupCount >> capacity;
    for (int i = 1; i <= groupCount; ++i) {
        int itemCount;
        cin >> itemCount;
        for (int j = 0; j <= capacity; ++j) {
            dp[i][j] = dp[i-1][j];
        }
        while (itemCount--) {
            int weight, value;
            cin >> weight >> value;
            for (int j = weight; j <= capacity; ++j) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - weight] + value);
            }
        }
    }
    cout << dp[groupCount][capacity] << '\n';
    return 0;
}

Multiple Knapsack Model

Basic Model

Given a knapsack with capacity V and n types of items, each with value v, weight w, and quantity s. Determine the maximum total value.

Convert each type into s identical items and solve as 0/1 knapsack. Time complexity O(n * V * s).

Example:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_CAPACITY = 205;
int dp[MAX_CAPACITY];

signed main() {
    int itemTypes, capacity;
    cin >> itemTypes >> capacity;
    for (int i = 1; i <= itemTypes; ++i) {
        int weight, value, quantity;
        cin >> weight >> value >> quantity;
        while (quantity--) {
            for (int j = capacity; j >= weight; --j) {
                dp[j] = max(dp[j], dp[j - weight] + value);
            }
        }
    }
    cout << dp[capacity] << '\n';
    return 0;
}

Binary Optimization Model

To reduce time complexity from O(n * V * s) to O(n * V * log(s)), split items into groups of sizes 1, 2, 4, ..., and the remainder, similar to binary representation.

Example:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_CAPACITY = 2e6;
int dp[MAX_CAPACITY];

signed main() {
    int itemTypes, capacity;
    cin >> itemTypes >> capacity;
    for (int i = 1; i <= itemTypes; ++i) {
        int volume, value, quantity;
        cin >> volume >> value >> quantity;
        for (int k = 1; k <= quantity; quantity -= k, k <<= 1) {
            for (int j = capacity; j >= k * volume; --j) {
                dp[j] = max(dp[j], dp[j - k * volume] + k * value);
            }
        }
        for (int j = capacity; j >= quantity * volume; --j) {
            dp[j] = max(dp[j], dp[j - quantity * volume] + quantity * value);
        }
    }
    cout << dp[capacity] << '\n';
    return 0;
}

Monotonic Queue Optimization for Multiple Knapsack

Algorithm Overview

Given N types of items with volume v[i], value w[i], and quantity s[i], and a knapsack of capacity V. Determine the maximum total value.

This optimization further improves the binary optimization by handling the logN part more efficiently.

State Transition Analysis

Define a 2D array dp[i][j] as the maximum value using first i types with capacity j. Not taking item i: dp[i-1][j] Taking k items of type i: dp[i-1][j-k*v] + k*w dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2*v]+2*w, ..., dp[i-1][j-k*v]+k*w) The first dimension can be rolled. If capacity is m, the answer is dp[n][m] or dp[m].