POJ1014-Dividing-多重背包
本代码中的几个函数可以作为“0-1背包”、“完全背包” 和“多重背包”的模板：
?
#include <iostream> #define INF 100000000 using namespace std; int f[240005]; //f[j]相当于f[i][j]: 考虑1...i个物品，恰好放到容量为j，所能达到的最大价值 int v; //背包容量 //处理一个完全背包 (该种物品不限量)void complete_pack(int *a, int c, int w) { for(int i = c; i <= v; i++) a[i] = max(a[i], a[i - c] + w); } //处理一个 01背包 (该种物品只有一个) void zeroone_pack(int *a, int c, int w) { for(int i = v; i >= c; i--) a[i] = max(a[i], a[i - c] + w); } //处理一个多重背包 (该种物品指定上限) void mutiple_pack(int *a, int c, int w, int m) { //该种物品足以塞满背包-->转化为完全背包 if(c * m >= v){ complete_pack(a, c, w); return; } /*二进制思想拆分：多重背包中的一个物品--变成-->0-1背包中的多个物品 容量：2^0 2^1 2^2 2^k m-∑前面 ***保证k达到最大值 价值：2^0*c 2^1*c 2^2*c 2^k*c (m-∑前面 )*c */ int k = 1; while(k < m) { zeroone_pack(a, k * c, k * w); m = m - k; k = 2 * k; } zeroone_pack(a, c * m, w * m); } int main() { //freopen("d:/data.in","r",stdin); //freopen("d:/data.out","w",stdout); int sum, i, c[7], w[7], m[7],cas = 0; while(scanf("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6])){ if(m[1] == 0 && m[2] == 0 && m[3] == 0 && m[4] == 0 && m[5] == 0 && m[6] == 0) break; sum = 0; for(i = 1; i <= 6; i++){ c[i] = w[i] = i; sum += c[i] * m[i]; } printf("Collection #%d:\n", ++cas); if(sum & 1){ puts("Can't be divided.\n"); }else{ sum /= 2; v = sum; for(i = 1; i <= sum; i++) f[i] = -INF; f[0] = 0; for(i = 1; i <= 6; i++) mutiple_pack(f, c[i], w[i], m[i]); if(f[v] < 0){ puts("Can't be divided.\n"); }else{ puts("Can be divided.\n"); } } } system("pause"); return 0; } ?