題目大意：分別給出價值為1~6的石頭的數量。問能否將這些石頭等價值平分。。。
解題思路:多重背包
1）多重背包的典型描述是這樣的:給出n種物品，背包的容量為V。每種物品的可用數量為num[i]，所占體積為c[i]，價值為w[i]，求。。。。。。
2)若以價值作為背包的容量，那麼很自然就能想到c[i] == w[i]
可先求出總價值sum，如果奇數，顯然不能，如果是偶數，由於石頭總數最多為M=20000，故其價值總和最多為C=20000×6=120000，（10^5）可設一數組flag【MAX_N]如果i可以取得，則flag【i】=1，否則等於0；剛開始是用母函數，O（N*M*C)，毫無懸念TLE，百度題解，發現01背包可以，還需要用到什麼二進制優化，不是很理解，不過按照思路寫了下，果真AC了，先寫後理解，多重背包+二進制優化，
多重背包問題：
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對於第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀態轉移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
復雜度是O(V*Σn[i])。
轉化為01背包問題另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為Σn[i]的01背包問題，直接求解，復雜度仍然是O(V*Σn[i])。
但是我們期望將它轉化為01背包問題之後能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價於取若干件代換以後的物品。另外，取超過n[i]件的策略必不能出現。
方法是：將第i種物品分成若干件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分別為 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種 物品分成系數分別為1,2,4,6的四件物品。
分成的這幾件物品的系數和為n[i]，表明不可能取多於n[i]件的第i種物品。另外這種方法也能保證對於0..n[i]間的每一個整數，均可以用若干個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，並不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉化為了復雜度為<math>O(V*Σlog n[i])的01背包問題，是很大的改進。
有兩點：
1、給定n，如何對n進行分組，使得[1,n]內的任一數等於若干組之和。可用1,2,4,8,16,....2^（k-1）,n-2^k+1這k+1個數組成。這個想的不是很通，求指點，啊，不需要了，忽然想到了，因為對於x屬於【2^k,n]內的數，t=x-(n-2^k+1)<2^k,而t可用前面幾組數組合而成，故x可用t+（n-2^k+1)組成。
2、為什麼只需要對這些分組進行dp就行了呢？可以這麼理解。本來基本狀態轉移方程是：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
而直接二進制優化後轉移方程為
然後再對每組濃縮了的物品（即1，2，4，8，....2^(k-1),n-2^k+1)進行01背包。由於【0，n】內的數均可有這些數組合，故全部01背包完後等價於f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}。理解有點繞腦，就這樣了，更多感覺在裡面。
2、二進制優化的原理簡單來說就是 一個數可以由一系列，全是2的倍數或者 2的倍數加上一個非2的倍數組成。
代碼如下：
* 1059_2.cpp
*
* Created on: 2013年8月13日
* Author: Administrator
*/
#include <iostream>
#include <stdio.h>
using namespace std;
int f[120005];
int num[7];
int V;
void ZeroOnePack(int cost, int weight) {
int v;
for (v = V; v >= cost; --v) {
f[v] = max(f[v], f[v - cost] + weight);
}
}
void CompletePack(int cost, int weight) {
int v;
for (v = cost; v <= V; ++v) {
f[v] = max(f[v], f[v - cost] + weight);
}
}
void MutiplePack(int cost, int weight, int amount) {
if (cost * amount >= V) {
CompletePack(cost, weight);
} else {
int k = 1;
while (k < amount) {
ZeroOnePack(k * cost, k * weight);
amount -= k;
k <<= 1;
}
if (amount > 0) {
ZeroOnePack(amount * cost, amount * weight);
}
}
}
int main() {
int count = 1;
while (scanf("%d%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &num[5],
&num[6]) != EOF, num[1] + num[2] + num[3] + num[4] + num[5] + num[6]) {
int i;
int total = 0;
for (i = 1; i <= 6; ++i) {
total += num[i] * i;
}
/**
* 如果總價值為奇數,一定不可分
*/
if (total % 2) {
printf("Collection #%d:\n", count++);
printf("Can't be divided.\n\n");
continue;
} else {
V = total / 2;
memset(f, 0, sizeof(f));
for (i = 1; i <= 6; i++) {
MutiplePack(i, i, num[i]);
}
/**
* 容量為V的背包的最大價值f[V]==V。那麼這種方案是成立的
* 怎麼理解呢???
* 前一個V可以理解成他需要裝滿的背包的容量為V，但實際裝不裝得滿,
* 那是不一定的。而題目要求我們選擇的是能裝滿的那種方案.
* 所以f[V] == v 的方案才算是成立的
*/
if (f[V] == V) {
printf("Collection #%d:\n", count++);
printf("Can be divided.\n\n");
} else {
printf("Collection #%d:\n", count++);
printf("Can't be divided.\n\n");
}
}
}
}
/*
* 1059_2.cpp
*
* Created on: 2013年8月13日
* Author: Administrator
*/
#include <iostream>
#include <stdio.h>
using namespace std;
int f[120005];
int num[7];
int V;
void ZeroOnePack(int cost, int weight) {
int v;
for (v = V; v >= cost; --v) {
f[v] = max(f[v], f[v - cost] + weight);
}
}
void CompletePack(int cost, int weight) {
int v;
for (v = cost; v <= V; ++v) {
f[v] = max(f[v], f[v - cost] + weight);
}
}
void MutiplePack(int cost, int weight, int amount) {
if (cost * amount >= V) {
CompletePack(cost, weight);
} else {
int k = 1;
while (k < amount) {
ZeroOnePack(k * cost, k * weight);
amount -= k;
k <<= 1;
}
if (amount > 0) {
ZeroOnePack(amount * cost, amount * weight);
}
}
}
int main() {
int count = 1;
while (scanf("%d%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &num[5],
&num[6]) != EOF, num[1] + num[2] + num[3] + num[4] + num[5] + num[6]) {
int i;
int total = 0;
for (i = 1; i <= 6; ++i) {
total += num[i] * i;
}
/**
* 如果總價值為奇數,一定不可分
*/
if (total % 2) {
printf("Collection #%d:\n", count++);
printf("Can't be divided.\n\n");
continue;
} else {
V = total / 2;
memset(f, 0, sizeof(f));
for (i = 1; i <= 6; i++) {
MutiplePack(i, i, num[i]);
}
/**
* 容量為V的背包的最大價值f[V]==V。那麼這種方案是成立的
* 怎麼理解呢???
* 前一個V可以理解成他需要裝滿的背包的容量為V，但實際裝不裝得滿,
* 那是不一定的。而題目要求我們選擇的是能裝滿的那種方案.
* 所以f[V] == v 的方案才算是成立的
*/
if (f[V] == V) {
printf("Collection #%d:\n", count++);
printf("Can be divided.\n\n");
} else {
printf("Collection #%d:\n", count++);
printf("Can't be divided.\n\n");
}
}
}
}
