洛谷P2392 背包问题

题目链接： 传送门

看完题目就感觉是个贪心，样例也能推过去，于是交了以下代码：

/*
 * @Author: hesorchen
 * @Date: 2020-04-14 10:33:26
 * @LastEditTime: 2020-05-13 14:29:51
 * @Link: https://hesorchen.github.io/
 */

#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define PI cos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000009
#define lowbit(abcd) (abcd & (-abcd))
#define fre                              \
    {                                    \
        freopen("in.txt", "r", stdin);   \
        freopen("out.txt", "w", stdout); \
    }

ll a1[50];
ll a2[50];
ll a3[50];
ll a4[50];
int main()
{
    ll s1, s2, s3, s4;
    cin >> s1 >> s2 >> s3 >> s4;
    for (int i = 1; i <= s1; i++)
        cin >> a1[i];
    for (int i = 1; i <= s2; i++)
        cin >> a2[i];
    for (int i = 1; i <= s3; i++)
        cin >> a3[i];
    for (int i = 1; i <= s4; i++)
        cin >> a4[i];
    ll ans = 0;
    sort(a1 + 1, a1 + 1 + s1, greater<int>());
    sort(a2 + 1, a2 + 1 + s2, greater<int>());
    sort(a3 + 1, a3 + 1 + s3, greater<int>());
    sort(a4 + 1, a4 + 1 + s4, greater<int>());
    ll pos;
    ll l, r;
    l = 1, r = 2;
    while (l <= s1)
    {
        if (a1[l] > 0 && a1[r] > 0)
            a1[l]--, a1[r]--;
        else if (a1[l] > 0)
            a1[l]--;
        ans++;
        if (a1[r] == 0 && a1[l] == 0)
            l += 2, r += 2;
        else if (a1[r] == 0)
            r += 1;
        else if (a1[l] == 0)
            l += 1, r += 1;
    }

    l = 1, r = 2;
    while (l <= s2)
    {
        if (a2[l] > 0 && a2[r] > 0)
            a2[l]--, a2[r]--;
        else if (a2[l] > 0)
            a2[l]--;
        ans++;
        if (a2[r] == 0 && a2[l] == 0)
            l += 2, r += 2;
        else if (a2[r] == 0)
            r += 1;
        else if (a2[l] == 0)
            l += 1, r += 1;
    }

    l = 1, r = 2;
    while (l <= s3)
    {
        if (a3[l] > 0 && a3[r] > 0)
            a3[l]--, a3[r]--;
        else if (a3[l] > 0)
            a3[l]--;
        ans++;
        if (a3[r] == 0 && a3[l] == 0)
            l += 2, r += 2;
        else if (a3[r] == 0)
            r += 1;
        else if (a3[l] == 0)
            l += 1, r += 1;
    }

    l = 1, r = 2;
    while (l <= s4)
    {
        if (a4[l] > 0 && a4[r] > 0)
            a4[l]--, a4[r]--;
        else if (a4[l] > 0)
            a4[l]--;
        ans++;
        if (a4[r] == 0 && a4[l] == 0)
            l += 2, r += 2;
        else if (a4[r] == 0)
            r += 1;
        else if (a4[l] == 0)
            l += 1, r += 1;
    }
    cout << ans << endl;

    return 0;
}

结果一个测试点都没过。看了一下题解，发现很多人都以为是贪心，果然没有经过系统证明的猜想都是耍流氓

解题思路：我们可以将每一门课的复习点分成两组，并且保证两组的差值尽可能小，那么就可以转换成01背包问题，背包的最大容量为$\frac{sum}{2}$2sum​，求出背包最多能装多少物品。结果就是$sum-\frac{sum}{2}$sum−2sum​

AC代码：

/*
 * @Author: hesorchen
 * @Date: 2020-04-14 10:33:26
 * @LastEditTime: 2020-05-13 14:57:12
 * @Link: https://hesorchen.github.io/
 */

#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define PI cos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000009
#define lowbit(abcd) (abcd & (-abcd))
#define fre                              \
    {                                    \
        freopen("in.txt", "r", stdin);   \
        freopen("out.txt", "w", stdout); \
    }

ll a1[50];
ll a2[50];
ll a3[50];
ll a4[50];

ll dp[500000];
int main()
{
    ll s1, s2, s3, s4;
    cin >> s1 >> s2 >> s3 >> s4;
    for (int i = 1; i <= s1; i++)
        cin >> a1[i];
    for (int i = 1; i <= s2; i++)
        cin >> a2[i];
    for (int i = 1; i <= s3; i++)
        cin >> a3[i];
    for (int i = 1; i <= s4; i++)
        cin >> a4[i];
    ll ans = 0;
    ll sum, sum_2;

    fill(dp, dp + 600, 0);
    sum = 0;
    for (int i = 1; i <= s1; i++)
        sum += a1[i];
    sum_2 = sum;
    sum = sum / 2;
    for (int i = 1; i <= s1; i++)
        for (int j = sum; j >= 0; j--)
            if (j >= a1[i])
                dp[j] = max(dp[j], dp[j - a1[i]] + a1[i]);
    ans += sum_2 - dp[sum];

    fill(dp, dp + 600, 0);
    sum = 0;
    for (int i = 1; i <= s2; i++)
        sum += a2[i];
    sum_2 = sum;
    sum = sum / 2;
    for (int i = 1; i <= s2; i++)
        for (int j = sum; j >= 0; j--)
            if (j >= a2[i])
                dp[j] = max(dp[j], dp[j - a2[i]] + a2[i]);
    ans += sum_2 - dp[sum];

    fill(dp, dp + 600, 0);
    sum = 0;
    for (int i = 1; i <= s3; i++)
        sum += a3[i];
    sum_2 = sum;
    sum = sum / 2;
    for (int i = 1; i <= s3; i++)
        for (int j = sum; j >= 0; j--)
            if (j >= a3[i])
                dp[j] = max(dp[j], dp[j - a3[i]] + a3[i]);
    ans += sum_2 - dp[sum];

    fill(dp, dp + 600, 0);
    sum = 0;
    for (int i = 1; i <= s4; i++)
        sum += a4[i];
    sum_2 = sum;
    sum = sum / 2;
    for (int i = 1; i <= s4; i++)
        for (int j = sum; j >= 0; j--)
            if (j >= a4[i])
                dp[j] = max(dp[j], dp[j - a4[i]] + a4[i]);
    ans += sum_2 - dp[sum];

    cout << ans << endl;

    return 0;
}