這道題我確實(shí)傻逼了……
多重背包+二進(jìn)制拆分優(yōu)化，如果dp[sum/2]=sum/2就說明能夠均分，否則不能均分。
我就是每想到一個(gè)事兒……如果sum是奇數(shù)直接果斷的不行，還有一個(gè)錯誤，就是把continue寫成了return 0……傻逼了……
view code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int max(int a, int b)
{
if (a > b) return a;
else return b;
}
int main()
{
int num[10], dp[120000], t, tot, i, j, sum, w[400000], n = 1;
bool ju = 1;
while (n)
{
sum = 0; tot = 0; ju = 1;
memset(w, 0, sizeof(w));
for (i = 1; i <= 6; i++)
{
cin >> num[i];
sum += num[i] * i;
if (num[i] != 0) ju = 0;
}
if (sum % 2 != 0)
{
cout << "Collection #" << n++ << ":" << endl << "Can't be divided." << endl << endl;
continue;
}
if (ju == 1) return 0;
for (i = 1; i <= 6; i++)
{
if (num[i] != 0)
{
tot++;
w[tot] = i;
num[i]--;
}
t = 2;
while (num[i] >= t)
{
num[i] -= t;
tot++;
w[tot] = i * t;
t *= 2;
}
if (num[i] > 0)
{
tot++;
w[tot] = num[i] * i;
}
}
memset(dp, 0, sizeof(dp));
for (i = 1; i <= tot; i++)
for (j = sum / 2; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
if (dp[sum / 2] == (sum / 2))
cout << "Collection #" << n++ << ":" << endl << "Can be divided." << endl << endl;
else cout << "Collection #" << n++ << ":" << endl << "Can't be divided." << endl << endl;
}
return 0;
}