取石子问题题解（C++ 实现）

一、题目分析

核心需求

给定$n$堆石子（每堆数量为$a_i$），最多选取$m$堆（$m \leq n$），要求选取的总石子数不超过$k$，求最大能取到的石子总数。

关键洞察

要在“堆数限制”和“总石子数限制”下最大化总和，最优策略是优先选择数量较小的石子堆。原因是：小堆石子能在有限堆数内，更灵活地凑出接近$k$的总和（若选大堆，可能堆数未到$m$但总和已超$k$）。

二、动态规划解法（通用高效）

适用于所有数据范围，尤其针对$n \leq 200$、$k \leq 2500$的$C$组数据，时间和空间复杂度均可控。

1. 解法思路

1. 排序预处理：将$a_i$从小到大排序，确保优先处理小堆石子（避免大堆占用堆数却超总和限制）。
2. DP状态定义：
   用二维布尔数组dp[j][s]表示“选取$j$堆石子，总数量为$s$”是否可行（true可行，false不可行）。
3. 初始化：dp[0][0] = true（选取0堆、总数量0是初始可行状态）。
4. 状态转移：
   对每堆石子$num$（排序后），从后往前遍历堆数$j$（$m \to 1$）和总数量$s$（$k \to num$），避免重复选取同一堆：
   若dp[j-1][s - num]可行（选$j-1$堆能凑出$s - num$），则dp[j][s]也可行（加当前堆$num$后，凑出$j$堆、$s$总数量）。
5. 结果查找：遍历所有堆数$j$（1到$m$），从最大总数量$k$往0找，第一个可行的$s$即为最大总和。

2. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 步骤1：将石子堆从小到大排序（优先选小堆，最大化总和）
    sort(a.begin(), a.end());
    
    // 步骤2：初始化DP数组（dp[j][s]：选j堆，总和s是否可行）
    // 堆数最多m，总和最多k，数组大小设为(m+1)×(k+1)
    vector<vector<bool>> dp(m + 1, vector<bool>(k + 1, false));
    dp[0][0] = true;  // 初始状态：0堆0石子可行
    
    // 步骤3：遍历每堆石子，更新DP状态
    for (int num : a) {
        // 从后往前遍历堆数j（避免重复选同一堆）
        for (int j = m; j >= 1; --j) {
            // 从后往前遍历总和s（s必须≥当前堆大小num，否则无法选）
            for (int s = k; s >= num; --s) {
                if (dp[j - 1][s - num]) {
                    dp[j][s] = true;
                }
            }
        }
    }
    
    // 步骤4：查找最大可行总和
    int ans = 0;
    for (int j = 1; j <= m; ++j) {  // 遍历所有可能的堆数（1~m）
        for (int s = k; s >= 0; --s) {  // 从最大限制k往0找
            if (dp[j][s]) {
                ans = max(ans, s);
                break;  // 当前堆数下最大s已找到，无需继续找更小值
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

3. 复杂度分析

• 时间复杂度：$O(n \times m \times k)$。$n$为堆数，$m$为最大选堆数，$k$为总石子数限制。对$n=200$、$m=200$、$k=2500$，计算量约$200 \times 200 \times 2500 = 10^8$，C++中可高效运行。
• 空间复杂度：$O(m \times k)$。二维数组存储状态，对$m=200$、$k=2500$，空间约$5 \times 10^4$，占用极小。

三、枚举解法（适用于$n \leq 20$的场景）

针对$B$组数据（$n \leq 20$、$k \leq 10^8$，DP空间不可行），通过二进制枚举所有选堆组合求解。

1. 解法思路

1. 排序预处理：将$a_i$从小到大排序，优先选小堆以最大化总和。
2. 二进制枚举：用$n$位二进制数mask表示选堆状态（第$i$位为1表示选第$i$堆）。
3. 组合筛选：对每个mask，统计选堆数量（二进制中1的个数）和总石子数，若堆数≤$m$且总和≤$k$，更新最大总和。

2. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 步骤1：从小到大排序，优先选小堆凑总和
    sort(a.begin(), a.end());
    
    int max_sum = 0;
    // 步骤2：二进制枚举所有选堆组合（mask从1到(1<<n)-1，代表所有非空组合）
    for (int mask = 1; mask < (1 << n); ++mask) {
        // 统计当前组合的堆数（二进制中1的个数）和总和
        int cnt = __builtin_popcount(mask);  // C++内置函数：统计二进制中1的数量
        int sum = 0;
        
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {  // 第i堆被选中（二进制第i位为1）
                sum += a[i];
                // 提前剪枝：若总和已超k，无需继续累加
                if (sum > k) {
                    break;
                }
            }
        }
        
        // 满足条件：堆数≤m，总和≤k，更新最大总和
        if (cnt <= m && sum <= k && sum > max_sum) {
            max_sum = sum;
        }
    }
    
    cout << max_sum << endl;
    return 0;
}

3. 复杂度分析

• 时间复杂度：$O(n \times 2^n)$。$n$为堆数，$2^n$是所有组合数，每个组合需遍历$n$位二进制统计总和。对$n=20$，$2^20 \approx 10^6$，计算量约$2 \times 10^7$，效率足够。
• 空间复杂度：$O(n)$。仅需存储石子堆数组，空间占用极小。

四、样例验证

样例输入

4 3 5
1 1 2 3

排序后数组

[1, 1, 2, 3]

动态规划/枚举结果

• 可选组合：选前3堆（1+1+2=4）或选1+2+3=6（超k=5）或选1+1+3=5（符合条件），最大总和为5，与样例输出一致。