今天看了下多重背包，理解的還不夠深入，不過因為是01背包過來的，所以接受起來很容易。
主要是運用了二進制的思想將一個數量為N很大的物品分為了logN個數量小的物品，而這logN個物品可以組成數量為0到N任意數量，所以這種策略是
成立的。
多重背包問題有TOJ1034，TOJ1670.
TOJ1034 :
大意是有6種規格的石頭，編號從1到6，編號為 i 的石頭的價值為 i .現在給出各種石頭的數量，問有沒有可能得到總價值的一半。
做法: DP, 每種石頭價值為v[i],價值為 i ，數量為 num[i] ,通過多重背包看能不能恰好取得總價值的一半。
一個優化是總價值為奇數直接不用考慮，而在DP的時候設置一個標記來記錄是否已經取得總價值一半，如果取得則可以返回。
做法2：這種方法的前提是POJ discuss里的一種做法，即給每個石頭的數量mod 8。證明是用抽屜原理證的，很復雜，我沒有看。但是這樣以來，數量
一下子大大減少，極大的提高了效率。
我說的做法2事實上是我的最初做法，即DFS，搜索，在搜索過程中注意剪枝，再加上數量取模的優化，復雜度也不高。
Code for 1034(Dividing):
import java.util.Scanner;
import java.util.*;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
public static int f[] = new int[20001*6]; // f[i]表示容量為 i 的背包最多能裝的物品的價值
public static int v[] = new int[7];
public static int num[] = new int[7];
public static int total,flag,key; //total為 6 種大理石的總價值 ，flag為標記，一旦為1表示可以取得，可以返回了
public static void onezeropack(int cost,int weight) { // 01背包函數，注意循環是從total 到 cost，不要弄反
int i;
for(i = total;i >= cost; i--) {
f[i] = Math.max(f[i],f[i-cost]+weight);
if(f[i] == key) { // 如果可以取得總價值一半，flag=1，返回
flag = 1;
return ;
}
}
}
public static void finishpack(int cost,int weight) {
int i;
if(flag==1) return ;
for(i = cost;i <= total; i++) {
f[i] = Math.max(f[i], f[i-cost]+weight);
if(f[i] == key) {
flag = 1;
return ;
}
}
}
public static void multipack(int cost,int weight,int amount) {
if(cost*amount >= total) {
finishpack(cost, weight);
return ;
}
if(flag==1) return ;
int k = 1;
while(k < amount) { // 該過程即為將一件物品拆分為1，2，4...2^k 件物品進行01背包過程
onezeropack(k*cost, k*weight);
amount -= k;
k *= 2;
}
onezeropack(cost*amount, weight*amount);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i,j,cas = 1;
while(true) {
Arrays.fill(f,0);
total = 0; flag = 0;
for(i = 1;i <= 6; i++) {
num[i] = in.nextInt();
v[i] = i;
total += i*num[i];
}
if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0)
break;
if(total%2==1) flag = 0;
else {
key = total/2;
for(i = 1;i <= 6; i++)
multipack(i, i, num[i]);
}
System.out.println("Collection #"+cas+":");
if(flag==0) System.out.println("Can't be divided.");
else System.out.println("Can be divided.");
System.out.println();
cas++;
}
}
}
TOJ 1670：
大意是一臺取款機有N中貨幣，每種貨幣面值為 V[i] ，數量為 num[i] , 給出一個價值，為在這個價值之內(包括這個價值)最大能取得多大。
分析：典型的多重背包，給出的價值即為背包容量，每種貨幣為一種物品，價值為v[i] , 數量為num[i]，求能得到的最大價值。
注釋就不加了，參考上面的程序
Code for 1670(Cash Mechine):
#include <cstdio>
#include <cstring>
int f[100002],v[12],num[12],cost[12];
int total,n;
int max(int a,int b){ return a>b?a:b;}
void OneZeroPack(int cost,int value){
int i,j;
for(i = total;i >= cost; i--)
f[i] = max(f[i],f[i-cost]+value);
}
void completePack(int cost,int weight){
int i;
for(i = cost;i <= total; i++)
f[i] = max(f[i],f[i-cost]+weight);
}
void multiPack(int cost,int weight,int amount){
if(cost*amount >= total){
completePack(cost,weight);
return ;
}
int k = 1;
while(k < amount){
OneZeroPack(k*cost,k*weight);
amount -= k;
k*=2;
}
OneZeroPack(cost*amount,amount*weight);
}
int main(){
int i,j,k;
while(scanf("%d%d",&total,&n)!= EOF){
memset(f,0,sizeof(f));
for(i = 1;i <= n; i++){
scanf("%d%d",&num[i],&cost[i]);
v[i] = cost[i];
}
for(i = 1;i <= n; i++)
multiPack(cost[i],v[i],num[i]);
printf("%d\n",f[total]);
}
}