昨天刷了一個(gè)最簡單的 01 背包，正好趁熱打鐵贬墩，多搞幾個(gè)背包的題邓梅。題目位于 Dividing啊鸭，copy 如下：
Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
Input
Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.
Output
For each collection, output "Collection #k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".
Output a blank line after each test case.
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can't be divided.
Collection #2:
Can be divided.
大意就是每組數(shù)據(jù)包含六個(gè)值，每個(gè)值代表的是擁有該權(quán)重的 marbles 的數(shù)量璧眠。求是否可以平均分配。換個(gè)角度，這其實(shí)就是一個(gè)完全背包問題蝌借，即是否可以完整裝滿一個(gè) total/2 的背包。
這道題提交了 10 次才 A 掉指蚁，4 次 Time Limit Exceeded菩佑，5 次 Runtime Error（都是數(shù)組越界造成的）。
下邊的代碼其實(shí)依然很亂（估計(jì)也沒人看）凝化，而且應(yīng)該仍有優(yōu)化空間稍坯，不過終究是 A 掉了，先貼出來搓劫，稍后在優(yōu)化瞧哟。
具體優(yōu)化有幾個(gè)點(diǎn)：
1、先計(jì)算 total枪向，total 為奇數(shù)時(shí)必然是不可分的勤揩。
2、大于 total/2 的值一律不用計(jì)算秘蛔。因?yàn)閷Y(jié)果沒有影響陨亡。
3傍衡、先處理奇數(shù)，再處理偶數(shù)负蠕。在處理偶數(shù)時(shí)聪舒，當(dāng) total/2 為偶數(shù)時(shí)，則只用計(jì)算偶數(shù)位虐急，反之則只用計(jì)算奇數(shù)位箱残。
4、循環(huán)時(shí)可以先計(jì)算出當(dāng)次循環(huán)最大的 index 和最小的 index止吁，過大或者過小的都沒必要處理被辑。
代碼如下：
#include <stdio.h>
#include<iostream>
using namespace std;
int MAX_LENGTH = 60000;
int n[7];
bool result[60002];
#define min(a, b) (a < b ? a : b)
int maxSum = 1;
int curTotal = 1;
int dividNum = 1;
// 處理奇數(shù)
void processOdd(int value) {
int number = n[value];
int minLoop = (curTotal - dividNum > 1 ? curTotal - dividNum : 1);
int maxLoop = min(maxSum, dividNum);
int tmp = 0;
int k = 0;
for (int t = maxLoop; t >= minLoop; t--) {
if (result[t]) {
for (k = number; k >= 1; k--) {
tmp = t + k * value;
if (tmp <= dividNum) {
result[tmp] = true;
if (maxSum < tmp) {
maxSum = tmp;
}
}
}
}
}
for (int i = 1; i <= number; i++) {
if (value * i <= dividNum) {
result[value * i] = true;
if (maxSum < value * i) {
maxSum = value * i;
}
}
}
curTotal += value * number;
}
// 處理偶數(shù)
void processEven(int value, bool isOdd) {
int number = n[value];
int minLoop = (curTotal - dividNum > 1 ? curTotal - dividNum : 1);
int maxLoop = min(maxSum, dividNum);
int tmp = 0;
int k = 0;
if ((maxLoop%2) != isOdd) {
maxLoop -= 1;
}
for (int t = maxLoop; t >= minLoop; t-=2) {
if (result[t]) {
for (k = number; k >= 1; k--) {
tmp = t + k * value;
if (tmp <= dividNum) {
result[tmp] = true;
if (maxSum < tmp) {
maxSum = tmp;
}
}
}
}
}
if (!isOdd) {
for (int i = 1; i <= number; i++) {
if (value * i <= dividNum) {
result[value * i] = true;
if (maxSum < value * i) {
maxSum = value * i;
}
}
}
}
curTotal += value * number;
}
void processResult(int num) {
memset(result, 0, sizeof(result));
maxSum = 1;
curTotal = 1;
dividNum = num;
for (int i = 1; i <=6; i+=2) {
if (n[i] != 0) {
processOdd(i);
}
}
for (int i = 2; i <= 6; i+=2) {
if (n[i] != 0) {
processEven(i, num%2 == 1);
}
}
}
int main(int argc, const char * argv[]) {
int total = 0;
int round = 0;
while (true) {
total = 0;
round++;
for (int i = 1; i <= 6; i++) {
scanf("%d", &n[i]);
total += (n[i] * i);
}
if (total == 0) {
return 0;
}
printf("Collection #%d:\n", round);
if (total % 2 != 0) {
printf("Can't be divided.\n\n");
continue;
}
int dividNum = total / 2;
processResult(dividNum);
if (!result[dividNum]) {
printf("Can't be divided.\n\n");
} else {
printf("Can be divided.\n\n");
}
}
}
如下的代碼邏輯比較簡單，但是會(huì)超時(shí)：
#include <stdio.h>
#include<iostream>
using namespace std;
int MAX_LENGTH = 60000;
int n[7];
bool result[60002];
#define min(a, b) (a < b ? a : b)
void processResult(int dividNum) {
int maxSum = 1;
int curTotal = 1;
for (int i = 1; i <= 6; i++) {
if (n[i] != 0) {
for (int k = 1; k <= n[i]; k++) {
int minLoop = (curTotal - dividNum > 1 ? curTotal - dividNum : 1);
for (int t = min(maxSum, dividNum); t >= minLoop; t--) {
if (result[t] && t + i <= dividNum) {
result[t + i] = true;
if (maxSum < t + i) {
maxSum = t + i;
}
}
}
curTotal += i;
if (i*k <= dividNum) {
result[i*k] = true;
if (maxSum < i*k) {
maxSum = i*k;
}
}
}
}
}
}
int main(int argc, const char * argv[]) {
int total = 0;
int round = 0;
while (true) {
total = 0;
round++;
for (int i = 1; i <= 6; i++) {
scanf("%d", &n[i]);
total += (n[i] * i);
}
if (total == 0) {
return 0;
}
printf("Collection #%d:\n", round);
if (total % 2 != 0) {
printf("Can't be divided.\n\n");
continue;
}
memset(result, 0, sizeof(result));
int dividNum = total / 2;
processResult(dividNum);
if (!result[dividNum]) {
printf("Can't be divided.\n\n");
} else {
printf("Can be divided.\n\n");
}
}
}
