自动搬运

查看原文

来自洛谷，原作者为

	mcturtle 求求了给个关注吧，壶关请在犇犇@，目前不互棕封灰蓝绿橙，橙及以上有勾或活跃必互||新一年级（小朋友多多关照）铁迷/飞友/MC and Bed Wars er(Easecation 97级)/现役OIer/……（成分复杂||ENTP喵

搬运于2025-08-24 23:13:42，当前版本为作者最后更新于2025-04-17 21:57:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

01 背包模版变形。

下面就是本题的思路了（较详细）：

准备工作：首先将这 $40$ 个数存储到 $a$ 数组中，随后将它们求和存储为 $sum$，$dp_0 \gets 0$。

由于我们只有选和不选两种选择，所以使用 bool 类型存储数组比较合适。

外层循环遍历这 $40$ 个数，内层循环从 $\frac{sum}{2}$ 遍历到当前外层循环遍历到的数 $a_i$（不包含 $a_i$）。

推导公式：$dp_i \gets dp_{i-a_i}$。通过遍历每个数，更新可能达到的和。

随后我们可以寻找最优解。从 $\frac{sum}{2}$ 开始，向下查找最大的可行和，并计算对应的乘积。

代码

$\texttt{C++}$：

#include <iostream>
using namespace std;
int a[]={5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231, 1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309};
long long sum,mx;
bool dp[1000005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    for(int i:a)sum+=i;
    sum/=2;
    dp[0]=1;
    for(int k:a){
        for(int i=sum;i>=k-1;i--){
            if(dp[i-k])dp[i]=1;
        }
    }
    for(int i=sum;i>=0;i--)if(dp[i]){mx=i;break;}
    long long p=mx*(sum*2-mx);
    cout<<p;
    return 0;
}

$\texttt{Py}$：

a = [
    5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231,
    1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,
    4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,
    7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309
]
t = sum(a)
h = t // 2
dp = [0] * (h + 1)
dp[0] = 1
for k in a:
    for i in range(h, k - 1, -1):
        if dp[i - k]:
            dp[i] = 1
m = 0
for i in range(h, -1, -1):
    if dp[i]:
        m = i
        break
r = m * (t - m)
print(r)