首页 > 代码库 > 分组背包——sicily 1750
分组背包——sicily 1750
1750. 运动会
限制条件
时间限制: 1 秒, 内存限制: 32 兆
题目描述
ZEH是一名04级的学生，他除了绩点高，还有运动细胞。有一次学院举办运动会，ZEH发现里面的 项目都是他所向披靡的，当然他想获得所有项目的No1，但是一个人的精力总是有限的，ZEH也是只有P(Power的简写，一个大于0且小于1000的整 数)的精力。如果精力足够参加比赛，一定能赢；相反，精力不够去参加比赛，Loss的概率很大，ZEH当然不想因为Loss而不爽。
整个运动会有N(大于0且小于等于100)项比赛，每项比赛都是在指定的一天D(D大于等于0)内举行完，但是一天可能同时有多个比赛同时进 行，ZEH当然就不能同时兼顾。比赛结束后，院长都会亲自为冠军颁发一定数额的奖金，其他名次只有一张奖状。ZEH当然是冲着奖金去的，他想获得最多的奖 金，师弟师妹们，你能帮ZEH大牛计算出他最多能拿多少奖金吗？
输入格式
第一行是一个整数T，表示这题有T个用例。
每个用例的第一行有两个正整数P N，分别表示ZEH的精力和比赛的项目。
第二行到第N+1行是N个项目，每一行有三个正整数D E M，分别表示这个项目在第D天举行，需要E的精力，和比赛的奖金。项目的顺序都按D排好序。
输出格式
对于每个用例，输出他能拿的最多的奖金。
样例输入
114 50 3 70 2 51 4 22 6 142 8 15
样例输出
23
刚开始的时候用一维dp[]去做，死活过不了，找了很久也没有找到原因，如果有哪位大神刚好看见，可以帮帮我查错。
后来改用了二维的dp[][]做，顺利的AC。
这一题题目本身就有问题，提纲上说D是正整数，但是例子里面给的D第一个就为0，这个我们先不管，考虑题目本身。
题目本身就是一个典型的分组背包问题，首先，将给定的项目按天分组，用合适的数据结构存储起来。
然后，按0-1背包的做法对天数进行选择，再在每天里对当天的项目做一个重复比较，最后一天只选到一个项目，原理和0-1背包是一致的。
核心代码：
1 for(int i=0;i<=D;i++){ 2 if(xmP[i].size()==0) 3 continue; 4 for(int j=P;j>=1;j--){ 5 if (i>0) 6 dp[i][j]=dp[i-1][j]; 7 for(int k=0;k<xmP[i].size();k++){ 8 if(xmP[i][k]<=j){ 9 if(i>0)10 dp[i][j]=max(dp[i][j],dp[i-1][j-xmP[i][k]]+xmM[i][k]);11 else12 dp[i][j]=max(dp[i][j],dp[i][j-xmP[i][k]]+xmM[i][k]);13 }14 }15 Max=max(Max,dp[i][j]);16 }17 }
对第0天的情况特殊处理了，还要注意dp[i][j]=max(dp[i][j],dp[i-1][j-xmP[i][k]]+xmM[i][k]);里的是dp[i][j]并不是dp[i-1][j]。
因为这里需要跟当天的上一个项目得出的结果做一个比较。
if (i>0) dp[i][j]=dp[i-1][j];
已经进行了初始化,所以一开始进入k的循环dp[i][j]就是当天不选项目即dp[i-1][j]的情况。
附上全部代码：
#include<iostream>#include<vector>#include<algorithm>#include<memory.h>using namespace std;int main(){ int T,P,N,D,E,M; int dp[101][1001]; vector<int> xmP[101]; vector<int> xmM[101]; cin>>T; while(T--){ cin>>P>>N; for(int i=0;i<101;i++){ xmP[i].clear(); xmM[i].clear(); } for(int i=0;i<N;i++){ cin>>D>>E>>M; xmP[D].push_back(E); xmM[D].push_back(M); } memset(dp,0,sizeof(dp)); int Max=0; for(int i=0;i<=D;i++){ if(xmP[i].size()==0) continue; for(int j=P;j>=1;j--){ if (i>0) dp[i][j]=dp[i-1][j]; for(int k=0;k<xmP[i].size();k++){ if(xmP[i][k]<=j){ if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j-xmP[i][k]]+xmM[i][k]); else dp[i][j]=max(dp[i][j],dp[i][j-xmP[i][k]]+xmM[i][k]); } } Max=max(Max,dp[i][j]); } } cout<<Max<<endl; } return 0;}
分组背包——sicily 1750
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。