牛能和牛可乐的礼物 题解

最优解：
看到这种题目描述，想到要就是变形的01背包问题，只不过体积和价值都是题目中给的“礼物价值”。
只要能想到这里，就可以想到把总体积的一半作为背包容量。01背包跑一下，得出的结果就是其中一个人拿到的礼物的总价值sum，然后另一个人得到的价值就是总价值减去sum，二者相减就是答案~
众所周知，背包的时间复杂度是物品个数x容积，空间复杂度是容积

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int price[50500],f[50500],n,t,sum;
int dp()
{
     memset(f,0,sizeof(f));
     for(int i=1;i<=n;i++)
     {
          for(int j=sum;j>=price[i];j--)
          {
               if(f[j]<f[j-price[i]]+price[i])
               f[j]=f[j-price[i]]+price[i];
          }
     }
     return f[sum];
}
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
               sum=0;
               for(int i=1;i<=n;i++)
               {
                    scanf("%d",&price[i]);
                    sum+=price[i];
               }
               int cnt=sum;
               sum=(sum+1)/2;
               cnt=dp()*2-cnt;
               if(cnt<0) cnt=-cnt;
               printf("%d\n",cnt);
    }
    return 0;
}

。。。。。。
写完题解才发现录题的格式选错了 QAQ
按着最小的改动 改了一下

class Solution {
public:
    /**
     *
     * @param n int整型 送来礼物的总个数
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        // write code here
        int n = presentVec.size();
        int f[10500];
         memset(f,0,sizeof(f));
        int sum = 0;
        for(int i = 0; i < n; i ++)
        {
            sum += presentVec[i];
        }
        int cnt = sum;
        sum = (sum+1)/2;
         for(int i = 0; i < n; i++)
         {
              for(int j = sum; j >= presentVec[i]; j --)
              {
                   if(f[j] < f[j-presentVec[i]] + presentVec[i])
                           f[j] = f[j - presentVec[i]] + presentVec[i];
              }
         }
         cnt = f[sum] * 2 - cnt;
        if(cnt < 0)
            cnt =- cnt;
        return cnt;
    }
};

下面这样写会好一些

class Solution {
public:
    /**
     *
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        // write code here
        int sum=accumulate(presentVec.begin(),presentVec.end(),0);
        vector<int>dp(sum/2+1);
        for(int i=0;i<presentVec.size();i++)
            for(int j=sum/2;j>=presentVec[i];j--)
                dp[j]=max(dp[j],dp[j-presentVec[i]]+presentVec[i]);
        return sum-2*dp[sum/2];
    }
};

。。。。。。
普通解：
非要说的话，就是二进制枚举遍历一下，那么时间复杂度是
很明显，这种方法又费时间，数据范围还不能太大。这段代码就不改了
反正也只能过一部分的数据
唯一的优点是空间复杂度低

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int price[50500],f[50500],n,t,sum;
int dp()
{
     memset(f,0,sizeof(f));
     for(int i=1;i<=n;i++)
     {
          for(int j=sum;j>=price[i];j--)
          {
               if(f[j]<f[j-price[i]]+price[i])
               f[j]=f[j-price[i]]+price[i];
          }
     }
     return f[sum];
}
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d", &n))
    {
               sum=0;
               for(int i = 0; i < n; i ++)
               {
                    scanf("%d", &price[i]);
                    sum += price[i];
               }
               int ans = sum;
               for (int i = 0; i < (1 << n); i ++) {
                    int tot = 0;
                    for (int j = 0; j < n; j ++) {
                        if (i & (1 << j )) {
                            tot += price[j];
                        }
                    }
                    if (ans > abs(tot * 2 - sum)) {
                        ans = abs(tot * 2 - sum);
                    }
               }
               printf("%d\n", ans);
    }
    return 0;
}