今天看了下多重背包，理解的還不夠深入，不過(guò)因?yàn)槭?1背包過(guò)來(lái)的，所以接受起來(lái)很容易。
主要是運(yùn)用了二進(jìn)制的思想將一個(gè)數(shù)量為N很大的物品分為了logN個(gè)數(shù)量小的物品，而這logN個(gè)物品可以組成數(shù)量為0到N任意數(shù)量，所以這種策略是
成立的。
多重背包問(wèn)題有TOJ1034，TOJ1670.
TOJ1034 :
大意是有6種規(guī)格的石頭，編號(hào)從1到6，編號(hào)為 i 的石頭的價(jià)值為 i .現(xiàn)在給出各種石頭的數(shù)量，問(wèn)有沒(méi)有可能得到總價(jià)值的一半。
做法: DP, 每種石頭價(jià)值為v[i],價(jià)值為 i ，數(shù)量為 num[i] ,通過(guò)多重背包看能不能恰好取得總價(jià)值的一半。
一個(gè)優(yōu)化是總價(jià)值為奇數(shù)直接不用考慮，而在DP的時(shí)候設(shè)置一個(gè)標(biāo)記來(lái)記錄是否已經(jīng)取得總價(jià)值一半，如果取得則可以返回。
做法2：這種方法的前提是POJ discuss里的一種做法，即給每個(gè)石頭的數(shù)量mod 8。證明是用抽屜原理證的，很復(fù)雜，我沒(méi)有看。但是這樣以來(lái)，數(shù)量
一下子大大減少，極大的提高了效率。
我說(shuō)的做法2事實(shí)上是我的最初做法，即DFS，搜索，在搜索過(guò)程中注意剪枝，再加上數(shù)量取模的優(yōu)化，復(fù)雜度也不高。
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 的背包最多能裝的物品的價(jià)值
public static int v[] = new int[7];
public static int num[] = new int[7];
public static int total,flag,key; //total為 6 種大理石的總價(jià)值 ，flag為標(biāo)記，一旦為1表示可以取得，可以返回了
public static void onezeropack(int cost,int weight) { // 01背包函數(shù)，注意循環(huán)是從total 到 cost，不要弄反
int i;
for(i = total;i >= cost; i--) {
f[i] = Math.max(f[i],f[i-cost]+weight);
if(f[i] == key) { // 如果可以取得總價(jià)值一半，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) { // 該過(guò)程即為將一件物品拆分為1，2，4...2^k 件物品進(jìn)行01背包過(guò)程
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：
大意是一臺(tái)取款機(jī)有N中貨幣，每種貨幣面值為 V[i] ，數(shù)量為 num[i] , 給出一個(gè)價(jià)值，為在這個(gè)價(jià)值之內(nèi)(包括這個(gè)價(jià)值)最大能取得多大。
分析：典型的多重背包，給出的價(jià)值即為背包容量，每種貨幣為一種物品，價(jià)值為v[i] , 數(shù)量為num[i]，求能得到的最大價(jià)值。
注釋就不加了，參考上面的程序
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]);
}
}