Big Event in HDU

上次做背包的时候写过这题 这次做母函数又碰到了...
背包解法(可以去这里看题意!!)")
首先我们还是将问题转换成求b的最大价值(具体可以看背包的题解)

题解

母函数解决的是什么问题?
它通常来求组合数 所以如果某个值有组合方案 我们找最大方案就行
所以我们只要找到离一半最近能组合的那个就行了

伪代码
for(int i=half;i>=0;i++)
{
    if(i是否有组合方案)
    {
        输出结果;
        break;
    }
}

AC代码

#include <iostream>
#include <cstring>
using namespace std;
int c1[2000000],c2[2000000];
int v[2000000],nums[2000000];
int main()
{
    int N;
    int c;
    while (cin >> N && N >= 0)
    {
        int s = 0;
        for (int i = 0; i < N; ++i) {
            cin >> v[i] >> nums[i];
            s += v[i]*nums[i];
        }
        int half = s/2;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for (int i = 0; i <= nums[0]; ++i)
            c1[i*v[0]] = 1;
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j <= half; ++j) {
                for (int k = 0; k <= v[i]*nums[i] && k+j <= half; k+=v[i]) {
                    c2[k+j] += c1[j];
                }
            }
            for (int l = 0; l <= half; ++l) {
                c1[l] = c2[l];
                c2[l] = 0;
            }
        }
        for (int i = half; i >= 0; --i) {
//            cout << i << " " << c1[i] << endl;
            if(c1[i])
            {
                cout << s - i << " " << i << endl;
                break;
            }
        }
    }
    return 0;
}
Last modification:April 11th, 2020 at 11:30 pm
如果觉得我的文章对你有用,请随意赞赏