多重背包問題
題目
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本算法
轉化為01背包問題
一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，
假如 一種物品的體積為2 數量為5 我們可以把其存在一個數組裡面存5次 然後進行01背包中的操作
則得到了物品數為∑n[i]的01背包問題，直接求解，複雜度仍然是O(V*∑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]間的每一個整數，均可以用若幹個系數的和表示
例如 3可以用1+2 表示 也就是說 選擇1和2對應的背包相當于選擇系數為3對應的背包 這樣就可以彌補系數為3的背包不存在的情況
像假如一種物品的體積為2 數量為5 我們可以把他分為 1 2 2 而不是1 1 1 1 1 少了2個 效率就高了 背包少了2個
這樣就将第i種物品分成了O(log n[i])種物品，将原問題轉化為了複雜度為O(V*∑log n[i])的01背包問題，是很大的改進。
看明白了吧 不明白的話要回去看看01和完全背包了 下面給個例子：
hdu 1059 Dividing（二進制轉化優化）
Dividing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5887 Accepted Submission(s): 1594
Problem 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 describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, ..., 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 colletcion, 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.
此題屬于多重背包，資料很大，需要二進制優化，不然逾時。優化後直接當做01背包來做，01背包是逆序！
連結：http://acm.hdu.edu.cn/showproblem.php?pid=1059
題目大意：
給你6個石子，石子的價值分别從1->t;6,然後輸入各個石子的數量。之後要你判斷石子能否分成兩堆，使兩堆石子的價值一樣。想了好久，最後覺得才發現可以用多重背包做。
解題思路：
首先這6種石子不是無數個的，而且石子有價值，可以假設石子的體積和價值一樣，反正題目都木有要求體積嘛。
一開始先算出石子的總價值，然後判斷總價值的奇偶性，如果是奇數，肯定分不了，偶數的話就多重背包下。以石子的總價值的一半作為背包。初始化為負無窮，如果最後h_tal是總價值的一半，dp[h_tal]如果有數量的話，那麼就證明這個價值可以達到，意思就是可以取石子取出價值為總價值的一半，那麼就滿足了題意要求的平均分為一半。
即如果能裝滿一半的背包 那必然能剩下一半 即能夠把總的val 分成兩份
ok,總的思路就是這樣了，思路相當的清晰啊，不過這樣做下去，直接就TLE了，因為這那個個總價值最多是20000*6，這可是120000/2啊， 然後3個for循環，最壞的複雜度就是6*120000/2*20000.不逾時才怪。
其實做個簡單的處理就可以了，把各種石子的數量模10就行了，因為一種石子超過10，比如12，那麼前面10個是肯定可以均分掉的，是以就 不考慮它了，直接考慮2就行了。。
也可以二進制壓縮 看下面壓縮代碼 如果看不懂 最下面有我的代碼 并且有解釋
代碼：
Cpp代碼
1 #include <iostream>
2 #include <stdio.h>
3 #include <memory.h>
4 using namespace std;
5
6 const int N = 6;
7 int V, total, sum;
8 int bag[120005];
9 int w[15], n[15], v[1005];
10
11 void _01_bag()
12 {
13 int i, j;
14 memset(bag, 0, sizeof(bag));
15 for(i = 0; i < total; i++)
16 {
17 for(j = sum; j >= v[i]; j--)
18 {
19 bag[j] = max(bag[j], bag[j-v[i]]+v[i]);//令其體積和價值相同
20 } //别忘記了上面的j是>=v[i]别忘記等号哈
21 }
22 }
23
24 int main()
25 {
26 int i, temp, zz = 1;
while(scanf("%d %d %d %d %d %d", &n[0], &n[1], &n[2], &n[3], &n[4], &n[5]))
27 {
28 if(n[0] + n[1] + n[2] + n[3] + n[4] + n[5] == 0) break;
29 printf("Collection #%d:\n", zz++);
30 V = 0;
31 for(i = 0; i < N; i++)
32 {
33 w[i] = i + 1;
34 V += w[i]*n[i]; //求總和
35 }
36 if(V%2 == 1) //總和是奇數則不能平分
37 {
38 printf("Can't be divided.\n\n");
39 continue;
40 }
41 sum = V/2; total = 0;
42 for(i = 0; i < N; i++) //二進制壓縮為//——01背包
43 {
44 if(n[i] == 0) continue;
45 temp = 1;
46 while(n[i] > temp)
47 {
48 v[total++] = temp*w[i]; //将新的值//賦給v[]
49 n[i] -= temp;
50 temp *= 2;
51 }
52 v[total++] = n[i]*w[i];
53 }
54 _01_bag(); //用新的v[]數組直接拿來01背包
55 if(bag[sum] != sum)
56 printf("Can't be divided.\n\n");
57 else
58 printf("Can be divided.\n\n");
59 }
60
61 return 0;
62 }
-----------------------------------我的代碼---------------------------------------
-----------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<string.h>
int b[10000];// 存的是二進制壓縮後的各個物體的價值
int c[120005];//這個要大啊 因為下面還有c[val]而val是總價值的一半是以很大
int bag(int val,int n)//它是01背包
{
int i,j;
memset(c,0,sizeof(c));
for(i=0;i<n;i++)//控制物體的個數 一個一個的解決 即加上這個物體後下面将列出所有的能裝下的情況
for(j=val;j>=b[i];j--)//在各個已裝體積下 騰出b[i]的空間把b[i]放進去 注意是各個體積下
{ c[j]=c[j]>c[j-b[i]]+b[i]?c[j]:c[j-b[i]]+b[i];//比較一下是放b[i]好 還是不放好
//printf("%d %d\n",c[val],val);}
if(c[val]==val) return 1;
else return 0;
}
int main()
{
int a[10],i,cnt=1,sum_v,val,temp,j;
while(1)
{
scanf("%d %d %d %d %d %d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5]);
sum_v=a[0]+a[1]*2+a[2]*3+a[3]*4+a[4]*5+a[5]*6;
if(sum_v==0) return 0;
printf("Collection #%d:\n",cnt++);
if(sum_v%2==1) {printf("Can't be divided.\n\n"); continue;}
val=sum_v/2;j=0;
for(i=0;i<6;i++)
{
if(a[i]==0) continue;
temp=1;
while(a[i]>temp)
{
b[j++]=temp*(i+1);
a[i]=a[i]-temp;
temp=temp*2;
}
b[j++]=a[i]*(i+1);//注意這裡哈 千萬不要寫成temp 一開始就一個勁錯這裡
}
if(bag(val,j)) printf("Can be divided.\n\n");//如果能夠分出一個能裝下一半價值的背包
else printf("Can't be divided.\n\n");//那麼剩下的是另一半 正好分成了2份
}
return 0;
}
大家複制下來看吧 不知道為什麼老是我複制的被擋住
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)