注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2191  

2012-08-02 14:01:03|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很明显的多重背包,因为好久没做多重背包的问题了,这里就详细的说明一下
多重背包可以有两种做法:
一种是转化成01背包做,时间复杂度为O(V*sum{n[i]});
另一种是根据二进制的思想,将一个物品拆成多个物品(1,2,4,8……),时间复杂度为O(V*sum{log n[i]})
下面列举以下两种做法的代码,具体注意的地方见代码:

转化成01背包问题的做法(两种写法,差别见代码):

/*
* fudq.cpp
*
* Created on: 2012-08-01
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
using namespace std;
struct Node
{
int jin,wei,kind;
};
Node node[102];
int n,m,k,s;
int f[102];

int max(int a,int b)
{
return a>b?a:b;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
#endif
int T,i,j,t;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&node[i].jin,&node[i].wei,&node[i].kind);
memset(f,0,sizeof(f));
for(i=0;i<m;i++)
for(t=0;t<node[i].kind;t++)//种类在外,价格在内
for(j=n;j>=node[i].jin;j--)
f[j]=max(f[j],f[j-node[i].jin]+node[i].wei);
printf("%d\n",f[n]);
}
return 0;
}




/*
* fudq.cpp
*
* Created on: 2012-08-01
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
using namespace std;
struct Node
{
int jin,wei,kind;
};
Node node[102];
int n,m,k,s;
int f[102];

int max(int a,int b)
{
return a>b?a:b;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
#endif
int T,i,j,t;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&node[i].jin,&node[i].wei,&node[i].kind);
memset(f,0,sizeof(f));
for(i=0;i<m;i++)
for(j=n;j>=node[i].jin;j--)//价格在外,个数在内
for(t=0;t<=node[i].kind && t*node[i].jin<=j;t++)
f[j]=max(f[j],f[j-t*node[i].jin]+t*node[i].wei);
printf("%d\n",f[n]);
}
return 0;
}


利用二进思想的做法:

/*
* fudq.cpp
*
* Created on: 2012-08-01
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
using namespace std;
struct Node
{
int jin,wei,kind;
};
Node node[102];
int n,m,k,s;
int f[102];

int max(int a,int b)
{
return a>b?a:b;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
#endif
int T,i,j,c,sum;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&node[i].jin,&node[i].wei,&node[i].kind);
memset(f,0,sizeof(f));
for(i=0;i<m;i++)//核心部分,具体写法慢慢理解
{
c=1;sum=0;
while(sum<node[i].kind)
{
for(j=n;j>=c*node[i].jin;j--)
f[j]=max(f[j],f[j-c*node[i].jin]+c*node[i].wei);
sum+=c;
c*=2;
if(c+sum>node[i].kind)
c=node[i].kind-sum;
}
}
printf("%d\n",f[n]);
}
return 0;
}


  评论这张
 
阅读(64)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018