题解：B4177 [BCSP-X 2024 6 月初中组] 尽量接近

Yxa_Sheep · 2025-07-06 15:23:03 · 题解

我写的和别的题解思路不大一样，但是纯正的 01 背包。状态定义与 01 背包相同，不会 01 背包就去搜搜吧，这里就不赘述了。

题目传送门

题意

从 n 个整数中选出一些数，让它们的总和尽量接近 k。

思路

我们设题目所给的原序列为 a，然后把它改成 01 背包：有 n 个物品，背包总容量为 k，第 i 件物品的重量为 a_i，价值也为 a_i。这时候就可以求出最接近 k 且小于等于 k 的那些数的和。我们再反过来想，把背包总容量变成 n-k，求出答案后用所有数的总和来减去它，就得到了最接近 k 且大于等于 k 的那些数的和。最后求得它们的最小值。我们还可以进行优化，我们在前面的步骤中已经求出的所有数的和，那么如果所有数的和都小于 k，我们就输出它，结束程序。细节看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, sum, ans, a[60], f[1000010];
int dp(int x) // x 为总容量
{
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
        for (int j = x; j >= a[i]; j--)
            f[j] = max(f[j], f[j - a[i]] + a[i]);
    return f[x];
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), sum += a[i];
    if (sum <= k)
        printf("%d", sum);
    else
    {
        if (abs(k - dp(k)) <= abs(k - (sum - dp(sum - k))))
            printf("%d", dp(k)); // 这里 dp(k) 一定小于 sum - dp(sum - k)
        else
            printf("%d", sum - dp(sum - k));
    }
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门