Problem Overview

Luogu P1509 "Finding a Girlfriend" presents a multi-constraint 0/1 knapsack problem. Given n items, each with three attributes rmb_i (money), rp_i (reputation), and time_i (time spent), the goal is to maximize the number of selected items such that the sum of rmb_i does not exceed m and the sum of rp_i does not exceed r. Among all solutions that achieve the maximum number of items, we need to minimize the total time_i.

Approach 1: Three-Dimensional DP

A direct multi-dimensional DP can be used. Define dp[j][k][l] as the minimum total time achievable with money ≤ j, reputtaion ≤ k, and exactly l items selected.

Initialize dp[j][k][0] = 0 for all valid j, k, and all other states to a large value (e.g., INF). Transition for each item i:

dp[j][k][l] = min(dp[j][k][l], dp[j-rmb_i][k-rp_i][l-1] + time_i)

After processing all items, the answer is dp[m][r][max_count] where max_count is the largest l such that dp[m][r][l] is not INF. This method runs in O(n²mr) time and uses O(nmr) space.

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

const int N = 105;
int n, m, r;
int rmb[N], rp[N], t[N], dp[N][N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &rmb[i], &rp[i], &t[i]);
    scanf("%d%d", &m, &r);
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= r; j++) dp[i][j][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= rmb[i]; j--)
            for (int k = r; k >= rp[i]; k--)
                for (int l = n; l >= 1; l--)
                    dp[j][k][l] = min(dp[j][k][l], dp[j-rmb[i]][k-rp[i]][l-1] + t[i]);
    for (int i = n; i >= 0; i--)
        if (dp[m][r][i] != 0x3f3f3f3f) { printf("%d", dp[m][r][i]); break; }
    return 0;
}

Approach 2: Dual Arrays for Two Objectives

Instead of a three-dimensional DP, we can use two separate DP tables: f[j][k] stores the maximum number of items, and g[j][k] stores the minimum time for that maximum count. This directly addresses the hierarchical objectives.

Initialize both arrays to zero (since no items selected is a valid state). For each item, update in reverse order:

• If selecting the item yields more items, update both f and g.
• If the count stays the same but total time is smaller, update g only.

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

const int N = 105;
int n, m, r;
int rmb[N], rp[N], t[N], f[N][N], g[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &rmb[i], &rp[i], &t[i]);
    scanf("%d%d", &m, &r);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= rmb[i]; j--)
            for (int k = r; k >= rp[i]; k--) {
                if (f[j][k] < f[j-rmb[i]][k-rp[i]] + 1) {
                    f[j][k] = f[j-rmb[i]][k-rp[i]] + 1;
                    g[j][k] = g[j-rmb[i]][k-rp[i]] + t[i];
                } else if (f[j][k] == f[j-rmb[i]][k-rp[i]] + 1)
                    g[j][k] = min(g[j][k], g[j-rmb[i]][k-rp[i]] + t[i]);
            }
    printf("%d", g[m][r]);
    return 0;
}

Time complexity is O(nmr), space is O(mr).

Approach 3: Combining Objectives via Encoding

A more compact approach combiens both objectives into a single value using a large constant M. Since item count is the primary objective, we can encode each item's value as M - time_i, where M is larger than any possible total time. Maximizing this encoded value will first maximize count (because each item adds at least M), and then minimize time (since subtracting time penalizes larger times).

We then solve a standard 0/1 knapsack maximizing the encoded value. Let dp[j][k] be the maximum encoded value achievable. The final answer (minimum total time) is recovered as M - (dp[m][r] % M), because dp[m][r] = count * M - total_time and total_time < M, so total_time = M - (dp[m][r] % M).

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

const int N = 105, M = 100010;
int n, m, r;
int rmb[N], rp[N], t[N], dp[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &rmb[i], &rp[i], &t[i]);
    scanf("%d%d", &m, &r);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= rmb[i]; j--)
            for (int k = r; k >= rp[i]; k--)
                dp[j][k] = max(dp[j][k], dp[j-rmb[i]][k-rp[i]] + M - t[i]);
    printf("%d", M - dp[m][r] % M);
    return 0;
}

This method also runs in O(nmr) time and O(mr) space, and is very concise.