我要啦免费统计
背包问题(01,完全,多重,未测试)
 
#define MAXN 120005  //maxcash
#define  MAX 11

int n[MAX],c[MAX];//n[i]物品i的数量,c[i]费用,w[i]价值 
int f[MAXN];//MAXN为最大容量 ,存储状态值 
int V,N;//V最大容量,N物品个数 

/*01背包物品 */ 
 
void ZeroOnePack(int cost,int weight){
      
//一件01背包物品 
      
// 费用cost, 价值weight,01背包 
     for(int v=V;v>=cost;--v)
      f[v]
=max(f[v],f[v-cost]+weight);
     
return;
 }

 
 
void ZeroOnePackMain(){
   
/*N件物品 容量为V的背包,第i件物品费用c[i],价值w[i],求转入背包可以获取的最大价值 
   原方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 
   简化方程:f[v]=max{f[v],f[v-cost]+weight};
   
*/

   
for(int i=0;i<N;i++)
      ZeroOnePack(cost[i],weight[i]);
   
return;
  }



  
/*一件完全背包*/ 
 
void CompletePack(int cost,int weight){
      
//一件物品完全背包 
      
//N 种物品 容量 V,c[i],w[i], 每一种无限,求最大价值  
    
// 费用cost, 价值weight,完全背包 
    
//对多种物品的问题,可以添加的优化:a.去掉大于V的物品;b.c[i]<=c[j] and w[i]>=w[j]去掉物品j   
    for(int v=cost;v<=V;++v)
       f[v]
=max(f[v],f[v-cost]+weight);
    
return;
 }



/*一件多重背包*/
 
void MultiplePack(int cost,int weight,int amount){
 
//多重背包 
 
//1种物品 费用cost, 价值weight,个数amount 
 
//二进制优化log(amount) 
     if(c*amount>=V){
        CompletePack(cost,weight);
       
return;      
     }

     
int k=1;
     
while(k<amount){
        ZeroOnePack(k
*cost);
        amount
-=k;
        k
*=2;
     }

     ZeroOnePack(amount
*cost);
     
return;
 }

posted on 2009-03-18 23:35 阅读(1760) 评论(2)  编辑 收藏 引用 所属分类: Dynamic programming

评论:
# re: 先写个背包问题模板(01,完全,多重,未测试) 2009-03-19 09:30 | cppexplore
偶尔往首页发个解题报告也无不可 大量的发而又重复的没啥意义吧
是不是可以写的总结啊 算法基础 npc综述之类的发到首页啊  回复  更多评论
  
# re: 先写个背包问题模板(01,完全,多重,未测试) 2009-03-19 18:02 | cdy20
@cppexplore
有些代码只算是保存而已。

我菜鸟而已。
也没多少时间写这些,写在笔记本上多点。

等退役后再说吧。
  回复  更多评论
  

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