自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:17:36，当前版本为作者最后更新于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;
}

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

题目传送门