二进制思想
问题描述：
假设有1000个苹果，现在要取n个苹果，如何取？正常的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。
又假设有1000个苹果和10只箱子，如何快速的取出n个苹果呢？可以在每个箱子中放 2^i (i<=0<=n)个苹果，也就是 1、2、4、8、16、32、64、128、256、489（最后的余数），相当于把十进制的数用二进制来表示，取任意n个苹果时，只要推出几只箱子就可以了。
多重背包问题
问题描述：
有N种物品和一个容量为V的背包。第 i 种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
问题分析：
很容易想到可以把该问题转化成01背包问题来考虑，把每n[i] 中的每个物品都当成一个独立的物品，而这 n[i] 个物品能够表示的重量其实用 log n[i]个组合后的物品就能表示。
内层循环代码如下：
int k, t;
k = 1;
t = n[i];
while(t > k)
{
for(j=W; j>=c[i]*k; --j)
{
f[j] = max(f[j], f[j-c[i]*k] + w[i]*k);
}
t -= k;
k *= 2;
}
for(j=W; j>=c[i]*t; --j)
{
f[j] = max(f[j], f[j-c[i]*t] + w[i]*t);
}
poj上的1014是一道简单的多重背包问题。http://poj.org/problem?id=1014
源码如下：
View Code
1 #include <stdio.h>
2 #define max(x, y) ((x)>(y) ? (x) : (y))
3 int f[80001];
4 int main()
5 {
6 int c[7];
7 int i, j;
8 int m = 0;
9 int nHarf = 0;
10 while(scanf("%d %d %d %d %d %d", &c[1], &c[2], &c[3], &c[4], &c[5], &c[6]) )
11 {
12 if(c[1]==0 && c[2]==0 && c[3]==0 && c[4]==0 && c[5]==0 && c[6]==0)
13 {
14 break;
15 }
16 printf("Collection #%d:\n", ++m);
17 nHarf = c[1]*1 + c[2]*2 + c[3]*3 + c[4]*4 + c[5]*5 + c[6]*6;
18 if(nHarf%2 == 1)
19 {
20 printf("Can't be divided.\n\n");
21 continue;
22 }
23 else
24 {
25 nHarf /= 2;
26 }
27 for(i=1; i<7; ++i)
28 {
29 if(c[i] == 0) continue;
30 if(c[i]*i > nHarf)
31 {
32 for(j=i; j<=nHarf; ++j)
33 {
34 f[j] = max(f[j], f[j-i] + i);
35 }
36 }
37 else
38 {
39 int k, t;
40 k = 1;
41 t = c[i];
42 while(t > k)
43 {
44 for(j=nHarf; j>=i*k; --j)
45 {
46 f[j] = max(f[j], f[j-i*k] + i*k);
47 }
48 t -= k;
49 k *= 2;
50 }
51 for(j=nHarf; j>=i*t; --j)
52 {
53 f[j] = max(f[j], f[j-i*t] + i*t);
54 }
55 }
56 }
57 if(f[nHarf] == nHarf)
58 {
59 printf("Can be divided.\n\n");
60 }
61 else
62 {
63 printf("Can't be divided.\n\n");
64 }
65 for(i=0; i<=nHarf; ++i)
66 {
67 f[i] = 0;
68 }
69 }
70 return 0;
71 }