题解 | #牛能和牛可乐的礼物#

#include <algorithm>
#include <cstdio>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        // write code here
        sort(presentVec.begin(), presentVec.end());
        int sum_of_all_present=0;
        for (int present:presentVec) {
            sum_of_all_present+=present;
        }
        int half=sum_of_all_present/2;
        vector<int> dp(half,0); //dp【i】表示拿的少的人，最多拿i+1的礼物，那实际能拿多少礼物
        if (dp.empty()) {
            return sum_of_all_present;
        }
        for (int present:presentVec) {//每增加一个礼物
            if (present==0) {
                continue;
            }
            for (int i=half-1; i>=0; i--) {
                if (dp[i]+present<=i+1) { //假如礼物可以加入，那直接放进去
                    dp[i]+=present;
                }else if (present>i+1) { //假如礼物不可能放进去，那直接丢弃
                    continue;
                }else if (dp[0]+present>i+1) { //假如礼物可以放进去，但是没法和其他礼物一起
                    if (present>dp[i]) {
                        dp[i]=present;
                    }
                }else{//礼物可以放进去，那么看看是和其他礼物一起放进去，还是丢弃
                    int j=i;
                    for (; j>0 && present+dp[j]>i+1; j--) { //找到最大的小于i+1的那个j
                    }
                    if (dp[j]+present>dp[i]) {
                        dp[i]=dp[j]+present;
                    }
                }
            }
        }
        return sum_of_all_present-2*dp[half-1];
    }
};

动态规划，C++