Abc 204 D - Cooking (01背包问题)

问题陈述

小日子要做 N 道菜，分别称为菜 1 到菜 N。

第 i 道菜可以用烤箱连续烤 Ti 分钟。一个烤箱不能同时烹饪两道或更多菜肴。

如果小日子有两个烤箱，那么烹制所有 N 道菜所需的最短时间是多少分钟？假设除使用烤箱以外的所有过程所花费的时间都可以忽略不计。

限制条件

1≤N≤100

1≤T i≤10 3

所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下：

N

T 1 ... T N

输出

打印答案。

输入示例 1

5

8 3 7 2 5

输出示例 1

13

例如，我们可以使用以下两个烤箱在 13 分钟内烹饪所有菜肴。

第一个烤箱 按此顺序烹制 5 号和 1 号菜肴。

第二个烤箱 按此顺序烹制菜肴 2、4 和 3。

输入示例 2

2

1000 1

样品输出 2

1000

样本输入 3

9

3 14 15 9 26 5 35 89 79

样本输出 3

138

-----

典型的01背包问题，就是将所有的元素放入2个背包，求他们放完后最小的差值的情况，返回较大的那个数，

这里就使用dp--我还不太熟，太笨了，LeetCode上记得有原题的。

dp[i][j]表示为从i个数中取和为j的数，能否取到，而最终的结论是从n个数中取多少个数，所以这里面设置数组的大小需要设定成dp[n+1][sum+1]，sum+1是为了计算方便，应该也可以取更大的值，但是不能更小的值，如果sum或者sum-1.。。。

01背包很久之前都接触过，但是没专题练习过，所以每次遇到了，就还是不太熟，不能马上写出来。

这里就是先设定数组的大小，明白数组的定义是什么，同时设定dp[0][0]=true,因为什么都不取，那么和肯定为0，这种情况是存在的，然后根据这个做一个2层循环，每种循环就设定2种情况，取还是不取，不取的话,dp[i+1][j]|=dp[i][j];(这里面就是dp[i+1][j]),取a[i]的话，值域就变成了从i+1个数，取和为j+a[i]的数，能否达到，如果dp[i][j]能达到，那么dp[i+1][j+a[i]]就能达到，这里就是或运算。（位运算中的）。但是这里面要加一个判定，就是j+a[i]不能大于sum。因为数组最大的和就是sum了，如果当前j+a[i]>sum了，就无意义了，会存在重复累加超过sum的情况？

最后输出，从n个数中取和 (从(sum+1)/2开始++)的数能否取到，能取到，就直接输出，return即可。