今天看了下多重背包，理解的还不够深入，不过因为是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]);
}
}