Overview

This problem extends the weight-limited 0/1 knapsack problem by adding \(K\) “lightweight cases” (which can halve an item’s weight). It is solved by adding a “number of cases used” dimension to the knapsack DP.

Discussion

Basic Observation

This problem is an extension of the standard 0/1 knapsack problem. Without the lightweight cases, it can be solved with the standard DP: \(dp[c] = \) maximum value obtainable within weight \(c\).

Problem with the Naive Approach

If we try all possibilities of “which gems to use the lightweight cases on,” there are \(\binom{N}{K}\) ways to choose \(K\) items from \(N\), which becomes enormous when \(K\) is large.

Solution

Noting that \(K \leq 30\) is small, we add “number of cases used so far” to the DP state. Specifically:

\[dp[k][c] = \text{maximum value when using } k \text{ cases with total weight at most } c\]

For each gem, we consider three choices: “put it in using a case,” “put it in without using a case,” or “don’t put it in.”

Algorithm

1. Initialize all \(dp[k][c]\) to \(0\) (\(0 \leq k \leq K\), \(0 \leq c \leq C\)).

2. For each gem \(i\), update using reverse-order loops similar to the 0/1 knapsack:

   • Iterate \(k\) from \(K\) down to \(0\)
   • Iterate \(c\) from \(C\) down to \(0\)
   • Case: put it in using a case (\(k > 0\) and \(c \geq \lfloor W_i/2 \rfloor\)): $\(dp[k][c] = \max(dp[k][c],\ dp[k-1][c - \lfloor W_i/2 \rfloor] + B_i)\)$
   • Case: put it in without using a case (\(c \geq W_i\)): $\(dp[k][c] = \max(dp[k][c],\ dp[k][c - W_i] + B_i)\)$

3. The answer is the maximum value among all \(dp[k][c]\).

Why the Reverse-Order Loop is Correct

This is a standard technique for the 0/1 knapsack. By updating \(c\) and \(k\) from larger values, we prevent selecting the same item more than once. The “put it in using a case” transition goes from \(dp[k-1][\cdot]\) to \(dp[k][\cdot]\), and since \(k\) is processed in descending order, we reference values from a state that has not yet considered the current gem.

Complexity

• Time complexity: \(O(N \cdot (K+1) \cdot (C+1))\)
  • The constraints guarantee \(N(K+1)(C+1) \leq 2 \times 10^7\)
• Space complexity: \(O((K+1) \cdot (C+1))\)

Implementation Notes

• The DP table is allocated as a 1-dimensional array (size \((K+1) \times (C+1)\)) rather than a 2-dimensional array, and accessed via pointer arithmetic to improve cache efficiency.

• Since the value \(B_i\) can be up to \(10^9\) and \(N\) can be up to \(10^5\), the total value requires the long long type.

• The “put it in using a case” transition references row dp[k-1], so a guard is needed to prevent execution when \(k=0\).

• Note that \(W_i\) can be up to \(2C\), so there may exist gems that cannot fit within the capacity without using a lightweight case.

  Source Code

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

int main() {
    int N, C, K;
    scanf("%d %d %d", &N, &C, &K);
    
    vector<int> B(N), W(N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &B[i], &W[i]);
    }
    
    int cols = C + 1;
    int sz = (K + 1) * cols;
    vector<long long> dp(sz, 0);
    
    for (int i = 0; i < N; i++) {
        int w = W[i];
        int wh = W[i] / 2;
        long long b = B[i];
        
        for (int k = K; k >= 0; k--) {
            long long* cur = dp.data() + (long long)k * cols;
            long long* prev = (k > 0) ? dp.data() + (long long)(k - 1) * cols : nullptr;
            
            for (int c = C; c >= 0; c--) {
                // Take with case
                if (k > 0 && c >= wh) {
                    long long val = prev[c - wh] + b;
                    if (val > cur[c]) cur[c] = val;
                }
                // Take without case
                if (c >= w) {
                    long long val = cur[c - w] + b;
                    if (val > cur[c]) cur[c] = val;
                }
            }
        }
    }
    
    long long ans = 0;
    for (int j = 0; j < sz; j++) {
        if (dp[j] > ans) ans = dp[j];
    }
    
    printf("%lld\n", ans);
    return 0;
}

This editorial was generated by claude4.6opus-thinking.