M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

多重背包问题

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



posted on 2010-07-07 20:18 M.J 阅读(640) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理