欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P2392 背包问题

程序员文章站 2022-06-08 14:27:56
...

题目链接: 传送门

洛谷P2392 背包问题
洛谷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背包问题,背包的最大容量为sum2\frac{sum}{2},求出背包最多能装多少物品。结果就是sumsum2sum-\frac{sum}{2}

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;
}