Common Advanced Variations of the Knapsack Problem
Multi-Dimensional Knapsack
Given N items and a knapsack with two constraints: maximum volume capacity V and maximum weight limit M. Each item i has volume c[i], weight w[i], and value v[i]. Find the maximum total value achievable without exceeding either constraint.
Unlike basic knapsack problems that only have one capacity constraint, multi-dimensional knapsack requires satisfying multiple constraints at once. The solution extends standard 0-1 knapsack logic by adding an extra dimension to the DP state.
We define dp[i][a][b] as the maximum value obtainable when considering the first i items, with total volume a and total weight b. Following the standard 0-1 knapsack derivation:
- If we do not select item i:
dp[i][a][b] = dp[i-1][a][b] - If we select item i:
dp[i][a][b] = dp[i-1][a - c[i]][b - w[i]] + v[i]
The final state value is the maximum of these two options. We can optimize space to 2 dimensions by iterating backwards from the maximum constraint values, just like in 0-1 knapsack.
Example: The Diver Problem
A diver needs at least m liters of oxygen and n liters of nitrogen to complete a dive. He has k available cylinders, each with a fixed amount of oxygen, fixed amount of nitrogen, and a fixed total weight. Find the minimum total weight of cylinders needed to meet his requirement.
Sample Input
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
Sample Output
249
This is a classic multi-dimensional knapsack problem. A useful optimization here: if the total oxygen or nitrogen exceeds the required amount, we can cap the value at the requirement since any extra provides no benefit.
#include<bits/stdc++.h>
using namespace std;
int ox[1010], ni[1010], weight[1010];
int min_dp[25][100];
int main(){
int req_ox, req_ni, k;
cin >> req_ox >> req_ni >> k;
for (int i = 1; i <= k; i++){
cin >> ox[i] >> ni[i] >> weight[i];
}
memset(min_dp, 0x7f7f7f, sizeof(min_dp));
min_dp[0][0] = 0;
for (int i = 1; i <= k; i++){
for (int j = req_ox; j >= 0; j--){
for (int l = req_ni; l >= 0; l--){
int prev_o = max(0, j - ox[i]);
int prev_n = max(0, l - ni[i]);
min_dp[j][l] = min(min_dp[j][l], min_dp[prev_o][prev_n] + weight[i]);
}
}
}
cout << min_dp[req_ox][req_ni];
return 0;
}
Grouped Knapsack
Given N items and a knapsack of capacity V. Items are divided into disjoint groups, and you can select at most one item from each group. Each item has a cost c[i] and value w[i]. Find the maximum total value that fits within the knapsack capacity.
Sample Input
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
Sample Output
20
This variation can be derived directly from 0-1 knapsack logic. Instead of choosing to take or not take each individual item, we choose to either take no item from a group, or take exactly one item from the group.
Loop order is critical for correctness. The outermost loop must iterate over each group. If you loop over items in the group first then iterate over capacity, you will allow multiple selections from the same group, which is incorrect. The correct order is:
- Outermost: iterate over each group
- Middle: iterate backwards over knapsack capacity
- Innermost: iterate over each item in the current group
Example Problem
A traveler has a backpack that can hold at most V kg. There are N items divided into T groups, at most one item can be chosen per group. Find the maximum total value.
Sample Input
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
Sample Output
20
This is a standard grouped knapsack template problem:
#include<bits/stdc++.h>
using namespace std;
int group_w[30][30], group_v[30][30], group_size[30], dp[300];
int main(){
int cap, total_items, total_groups;
cin >> cap >> total_items >> total_groups;
for (int i = 1; i <= total_items; i++){
int w, val, g;
cin >> w >> val >> g;
group_size[g]++;
group_w[g][group_size[g]] = w;
group_v[g][group_size[g]] = val;
}
for (int i = 1; i <= total_groups; i++){
for (int j = cap; j >= 0; j--){
for (int k = 1; k <= group_size[i]; k++){
if (j >= group_w[i][k]){
dp[j] = max(dp[j], dp[j - group_w[i][k]] + group_v[i][k]);
}
}
}
}
cout << dp[cap];
return 0;
}
Generalized Knapsack
In some knapsack problems, the value of an item is not fixed; it depends on how much capacity you allocate to it. Allocating more capacity gives a different value than allocating less. This type of problem can be solved similarly to an unoptimized unbounded knapsack: we enumerate all possible capacity allocations for each item and pick the optimal result.
Since the knapsack has a fixed maximum capacity, we only need to check allocations up to that maximum. For each item, we try every possible amount of space we could assign to it, updating the DP state to get the maximum value.
Example Problem
Given a knapsack of capacity m ≤ 1000, and n ≤ 1000 items. Each item's value follows the formula w = a_i² * k + b_i * k + c_i where k is the amount of capacity allocated to the item (k ≥ 1). Find the maximum total value that fits within capacity m.
Sample Input
6 100
1 5 5
-1 1 -5
-8 9 5
2 -1 4
7 7 5
2 0 -10
Sample Output
7305
This is a classic generalized knapsack problem:
#include<bits/stdc++.h>
using namespace std;
int a[1010], b[1010], c[1010], dp[1010];
int main(){
int n, cap;
cin >> n >> cap;
for (int i = 1; i <= n; i++){
cin >> a[i] >> b[i] >> c[i];
}
for (int i = 1; i <= n; i++){
for (int j = cap; j >= 0; j--){
for (int k = 1; k <= j; k++){
int val = a[i] * a[i] * k + b[i] * k + c[i];
dp[j] = max(dp[j], dp[j - k] + val);
}
}
}
cout << dp[cap];
return 0;
}
Dependent Knapsack
Dependent knapsack problems have relationships between items: some items (called attachments) can only be selected if you also select their corresponding main item. A main item can exist without any attachments, but attachments cannot exist without they main item. The most common simpler variant of this problem is when each main item has at most two attachments, and attachments do not have their own sub-attachments, which can be solved directly with 0-1 knapsack logic.
Example: NOIP2006 Jinming's Budget Plan
Jinming wants to buy items, split into main items and attachments. To buy an attachment you must first buy its main item. Each main item can have 0, 1, or 2 attachments. Each item has a price and an importance, we want to maximize the sum of price * importance without exceeding the total budget.
Sample Input
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
Sample Output
2200
Since each main item can have at most two attachments, there are only 5 valid combinations for each main item:
- Do not take anything
- Take only the main item
- Take the main item + first attachment
- Take the main item + second attachment
- Take the main item + both attachments
We check all combinations that fit within the current budget and take the maximum result.
#include <bits/stdc++.h>
using namespace std;
int main_cost[100], main_val[100];
int att_cost[100][3], att_val[100][3];
int dp[32001];
int main() {
int budget, total_items;
cin >> budget >> total_items;
for (int i = 1; i <= total_items; i++){
int v, p, q;
cin >> v >> p >> q;
if (q == 0){
main_val[i] = v * p;
main_cost[i] = v;
}else {
att_cost[q][0]++;
att_cost[q][att_cost[q][0]] = v;
att_val[q][att_cost[q][0]] = v * p;
}
}
for (int i = 1; i <= total_items; i++){
if (main_cost[i] == 0) continue;
for (int j = budget; j >= main_cost[i]; j--){
// Only main item
dp[j] = max(dp[j], dp[j - main_cost[i]] + main_val[i]);
// Main + first attachment
if (j >= main_cost[i] + att_cost[i][1]){
dp[j] = max(dp[j], dp[j - main_cost[i] - att_cost[i][1]] + main_val[i] + att_val[i][1]);
}
// Main + second attachment
if (j >= main_cost[i] + att_cost[i][2]){
dp[j] = max(dp[j], dp[j - main_cost[i] - att_cost[i][2]] + main_val[i] + att_val[i][2]);
}
// Main + both attachments
if (j >= main_cost[i] + att_cost[i][1] + att_cost[i][2]){
dp[j] = max(dp[j], dp[j - main_cost[i] - att_cost[i][1] - att_cost[i][2]] + main_val[i] + att_val[i][1] + att_val[i][2]);
}
}
}
cout << dp[budget];
return 0;
}
Counting Knapsack Solutions
A common extension of the 0-1 knapsack problem asks to count how many different ways exist to achieve the optimal result. The approach is straightforward: we first compute the maximum achievable value/volume, then run a second DP to count the number of ways to reach that optimal result.
Example Problem
Given a knapsack of capacity m, n items each with volume v[i]. Find the minimum possible remaining capacity, and the number of different ways to achieve this minimum remaining capacity.
Sample Input
99 8
3 5 8 13 21 34 55 89
Sample Output
2
6
We first run a standard 0-1 knapsack to find the maximum total volume we can fit, then run a counting DP to get the number of ways to reach that total volume.
#include<bits/stdc++.h>
using namespace std;
int vol[2010];
long long dp[20010], count_dp[20010];
int main() {
int cap, n;
cin >> cap >> n;
for (int i = 1; i <= n; i++){
cin >> vol[i];
}
for (int i = 1; i <= n; i++){
for (int j = cap; j >= vol[i]; j--){
dp[j] = max(dp[j], dp[j - vol[i]] + vol[i]);
}
}
long long max_used = dp[cap];
cout << cap - max_used << endl;
count_dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = max_used; j >= vol[i]; j--) {
count_dp[j] += count_dp[j - vol[i]];
}
}
cout << count_dp[max_used];
return 0;
}
Reconstructing 0-1 Knapsack Solution with Minimum Lexicographic Order
Given N items and a knapsack of capacity V, each item can be used once. Find the maximum total value, and output the sequence of selected item indices with the smallest lexicographic order.
Sample Input
4 5
1 2
2 4
3 4
4 6
Sample Output
1 4
To get the minimum lexicographic order, we reverse the order of DP processing: we start from the last item and move to the first, building the DP table from back to front. Then we can greedily pick the smallest index possible when reconstructing the solution.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int vol[MAX], val[MAX], dp[MAX][MAX];
int main() {
int n, cap;
cin >> n >> cap;
for (int i = 1; i <= n; i++){
cin >> vol[i] >> val[i];
}
for (int i = n; i >= 1; i--){
for (int j = 0; j <= cap; j++) {
dp[i][j] = dp[i+1][j];
if (j >= vol[i]){
dp[i][j] = max(dp[i][j], dp[i+1][j - vol[i]] + val[i]);
}
}
}
int remaining = cap;
for (int i = 1; i <= n; i++){
if (remaining >= vol[i] && dp[i][remaining] == dp[i+1][remaining - vol[i]] + val[i]) {
cout << i << ' ';
remaining -= vol[i];
}
}
return 0;
}
