Problem Statement

Given n items, each with weight weight[i], value value[i], and group index group[i], pack them in to a knapsack with maximum capacity W. Each group can contain at most one item. Find the maximum total value.

Solution 1: Two-Dimensional DP Array

This is a classic grouped knapsack problem. First, we need to process all items similar to 0-1 knapsack. We can store indices of items belonging to the same group in vectors. Since group[i] may have large integer values, we remap them to consecutive indices from 1 to k (where k is the total number of groups).

Since each group allows at most one item, the state transition must come from the previous group. We need an extra dimension to track groups, so we define dp[g][c] as the maximum value achievable using the first g groups with knapsack capacity c.

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

const int MAX_N = 1010;
const int MAX_G = 105;
int capacity, itemCount, groupCount;
int weight[MAX_N], worth[MAX_N], grp[MAX_N];
int64 dp[MAX_G][MAX_N];
unordered_map<int, int> groupMap;
vector<int> members[MAX_G];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> capacity >> itemCount;
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weight[i] >> worth[i] >> grp[i];
    }
    
    for (int i = 1; i <= itemCount; ++i) {
        if (groupMap.count(grp[i])) {
            grp[i] = groupMap[grp[i]];
        } else {
            grp[i] = groupMap[grp[i]] = ++groupCount;
        }
        members[grp[i]].push_back(i);
    }
    
    for (int g = 1; g <= groupCount; ++g) {
        for (int c = 0; c <= capacity; ++c) {
            dp[g][c] = dp[g - 1][c];
        }
        
        for (int idx : members[g]) {
            for (int c = capacity; c >= weight[idx]; --c) {
                dp[g][c] = max(dp[g][c], dp[g - 1][c - weight[idx]] + worth[idx]);
            }
        }
    }
    
    cout << dp[groupCount][capacity];
    return 0;
}

Solution 2: One-Dimenisonal DP Array

Notice that the two nested loops—the iteration over items in the current group and the backward itreation over capacities—are independent of each other. By swapping the loop order, with the outer loop iterating over capacities and the inner loop iterating over items, we can compress the DP array to a single dimension. In this arrangement, dp[capacity - weight[i]] won't be updated before dp[capacity] is computed.

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

const int MAX_N = 1010;
const int MAX_G = 105;
int capacity, itemCount, groupCount;
int weight[MAX_N], worth[MAX_N], grp[MAX_N];
int64 dp[MAX_N];
unordered_map<int, int> groupMap;
vector<int> members[MAX_G];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> capacity >> itemCount;
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weight[i] >> worth[i] >> grp[i];
    }
    
    for (int i = 1; i <= itemCount; ++i) {
        if (groupMap.count(grp[i])) {
            grp[i] = groupMap[grp[i]];
        } else {
            grp[i] = groupMap[grp[i]] = ++groupCount;
        }
        members[grp[i]].push_back(i);
    }
    
    for (int g = 1; g <= groupCount; ++g) {
        for (int c = capacity; c >= 0; --c) {
            for (int idx : members[g]) {
                if (c >= weight[idx]) {
                    dp[c] = max(dp[c], dp[c - weight[idx]] + worth[idx]);
                }
            }
        }
    }
    
    cout << dp[capacity];
    return 0;
}

Complexity Analysis

• Time Complexity: Both solutions run in O(k × W × s) where k is the number of groups, W is the knapsack capacity, and s is the average group size. In the worst case (each item in its own group), this becomes O(n × W).

• Space Complexity: Solution 1 uses O(k × W) space, while Solution 2 optimizes to O(W) space using single-dimensional DP with modified loop ordering.