描述
hwf 是一个非常喜欢吃披萨的人。某天，天上掉下了一张披萨，被 hwf 和高老师看到了。
高老师把披萨分成了 n 份, 第 i 份的角度为 ai。为了公平起见，他们决定由 hwf 把 n 份披萨分成两堆，然后高老师肯定会挑一堆角度和多的，hwf 拿剩下的一堆。hwf 想吃到尽可能多的披萨，但是 hwf 的心思已经全在吃披萨上了。
快帮助 hwf，告诉他最多能吃到多少披萨吧！
题目链接
https://citel.bjtu.edu.cn/acm/problem/1844
输入数据
第一行为一个整数 t (1≤t≤500)，表示数据的组数。接下来对于每组数据：
第一行有一个整数 n (2≤n≤360)，表示披萨被分成的份数。
第二行有 n 个整数 a1,a2,…,an (1≤ai<360)，分别表示第 i 份披萨的角度。
保证 ∑ai=360
输出数据
对于每组数据，输出一行：
第一行为一个整数，表示hwf最多可以吃到披萨的角度数。
样例输入
2
4
10 130 170 50
3
200 60 100
样例输出
180
160
题目分析
n 最大为360，如果使用搜索肯定会超时。
动态规划。
题目可以转化为往容积为180的箱子里放披萨，最多能放多少披萨🍕？
设num[i]表示第 i 块披萨的角度；res[i][j]表示在前 i 块披萨中选择若干披萨放入容积为 j 的箱子里，能放入的披萨角度和的最大值。
num[i] > j时，第 i 块披萨不能放入容积为 j 的箱子中，易得res[i][j] = res[i-1][j]
num[i] <= j时，如果第 i 块披萨不放入箱子，则res[i][j] = res[i-1][j]；如果第 i 块披萨放入箱子，则res[i][j] = num[i] + res[i-1][j-num[i]]；所以有res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]])
综上所述，我们得到了下面的递推关系式
if (num[i] > j)
res[i][j] = res[i - 1][j];
else
res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]]);
我们会发现，res[i][j]只和下标比它小的res[i - 1][j]以及res[i - 1][j - num[i]]有关，所以我们可以使用两层循环将 res 数组所有的值都计算出来。
需要对 res 数组进行一些初始化工作，才能通过递推求出后面的值。
res[n][180]就是问题的答案。
AC代码1
上面分析中，res 的第一维下标是从 1 开始的，代码中的是从 0 开始的。
在代码中，res[n-1][180]是最终答案。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int num[365], n, t, i, j, res[365][185];
cin >> t;
while (t--)
{
memset(res, 0, sizeof(res));
cin >> n;
for (i = 0; i < n; i++)
cin >> num[i];
for (j = 180; j >= num[0]; j--)
res[0][j] = num[0];
for (i = 1; i < n; i++)
{
for (j = 1; j <= 180; j++)
{
if (num[i] > j)
res[i][j] = res[i - 1][j];
else
res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]]);
}
}
cout << res[n - 1][180] << endl;
}
return 0;
}
AC代码2
大家会发现，res[i][j]在第一维度上只和res[i-1]有关。
所以res数组的第一个维度其实可以省略。
另外，在j < num[i]时，res[i][j] = res[i-1][j]，在省略了第一维度后，这个也可以不写了，因为res[j] = res[j]
#include <bits/stdc++.h>
using namespace std;
int main()
{
int num[365], n, t, i, j, res[185];
cin >> t;
while (t--)
{
memset(res, 0, sizeof(res));
cin >> n;
for (i = 0; i < n; i++)
cin >> num[i];
for (i = 0; i < n; i++)
for (j = 180; j >= num[i]; j--)
res[j] = max(res[j], num[i] + res[j - num[i]]);
cout << res[180] << endl;
}
return 0;
}