多重背包的拆分问题

el/2024/5/21 22:16:49

多重背包应该算是背包问题里面比较麻烦的一种了,基本思路就是拆分转化为01背包,进而套01背包的模版

今天在洛谷刷题的时候遇到一道题,是一个多重背包和完全背包的组合型问题

题目描述

爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看Ai遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。

输入

共n+1行:

第1行:三个数:现在时间Ts(几点:几分),去上学的时间Te(几点:几分),爱与愁大神院子里有几棵樱花树n。

第2行~第n+1行:每行三个数:看完第i棵树的耗费时间Ti,第i棵树的美学值Ci,看第i棵树的次数Pi(Pi=0表示无数次,Pi是其他数字表示最多可看的次数Pi)。

输出

只有一个整数,表示最大美学值。

样例输入
6:50 7:00 3
2 1 0
3 3 1
4 5 4
样例输出
11

这道题我一开始的思路是用时间的限制求出完全背包的上限,然后将完全背包转换为多重背包,进而进行拆分,就可以套01背包的板子

这是一个我作为一名蒟弱 的的第一反应

交完之后很尴尬的,除了第一个点都TLE了,后来发现这道题在拆分的时候要用到2进制拆分

二进制拆分:

方法:

将一个数字用根据2的多少次方进行拆分,如:

7=1+2+4;

9=1+2+4+2;

这样做的好处就是减少了占用的空间,并且将拆分数字组合相加可以得到(1~n)之间的任何一个数字,并且组合方式较少

而如果采用拆分成1的话,就会产生较多的组合方式,造成了重复运算

最后,上面那道题的代码

#include <iostream>
#include <stdio.h>
using namespace std;
int sumt,num,x,y,z,T[100005],M[100005],ans[10001];
int main(){int h1,h2,m1,m2,n;scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&n);sumt=h2*60+m2-h1*60-m1;for (int i = 0; i < n; ++i){cin>>x>>y>>z;if(z==0)z=sumt/x+1;int t=1;while(z){T[num]=t*x;M[num]=t*y;z-=t;t*=2;num++;if(z<=t){T[num]=z*x;M[num]=z*y;num++;break;}}}for (int i = 0; i <= num; ++i){for (int j = sumt; j >= T[i]; --j){ans[j]=max(ans[j],ans[j-T[i]]+M[i]);}}cout<<ans[sumt]<<endl;}

http://www.ngui.cc/el/5239386.html

相关文章

D. a-Good String

传送门 题意 一个字符串如果长度为1 并且为’a’ 那么就是 a -good 字符串&#xff0c; 当长度大于1时&#xff0c; 需要满足 &#xff1a; 将总区间划分成一半&#xff0c; 其中一半全是a&#xff0c;另一半必须为b-good 字符串 以此类推 分析 这道题的做法比较直观&#…

大师 洛谷P4933

大师 题目链接 大师 题目描述 建筑大师最近在跟着数学大师ljt12138学数学&#xff0c;今天他学了等差数列&#xff0c;ljt12138决定给他留一道练习题。 ljt12138首先建了n个特斯拉电磁塔&#xff0c;这些电塔排成一排&#xff0c;从左到右依次标号为1到n&#xff0c;第i个…

C. Good String

传送门 分析 给你一串字符串&#xff0c;你可以擦去一部分字符&#xff0c;剩下一个字符串t,要求最后剩下的字符串t满足这样的性质&#xff1a;字符串&#x1d461;2&#x1d461;3…&#x1d461;&#x1d45b;−1&#x1d461;&#x1d45b;&#x1d461;1和字符串 &#x…

Travel 最短路

链接&#xff1a;https://ac.nowcoder.com/acm/problem/14292 来源&#xff1a;牛客网 题目描述 精灵王国有N座美丽的城市&#xff0c;它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i1座城市花费的时间为d[i]。特别地&#xff0c;第N座城市到第1座城市花费的时间为…

飞行路线 |分层图初步学习

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15073 来源&#xff1a;牛客网 题目描述 Alice和Bob现在要乘飞机旅行&#xff0c;他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务&#xff0c;设这些城市分别标记为0到n-1&#xff0c;一共有m种航…

设计密码 —— 状态机

来源&#xff1a;acwing 题目描述 你现在需要设计一个密码 S&#xff0c;S 需要满足&#xff1a; S 的长度是 N&#xff1b; S 只包含小写英文字母&#xff1b; S 不包含子串 T&#xff1b; 例如&#xff1a;abc 和 abcde 是 abcde 的子串&#xff0c;abd 不是 abcde 的子串…

A. Remove Smallest

传送门 分析 这道题的意思大概是说有一串数字&#xff0c;你每次可以取出两个数字x&#xff0c;y&#xff0c;但要求是x和y相差不能超过1&#xff0c;然后你可以任意删去一个数字&#xff0c;这种操作可以进行无数次。 给你一个数组&#xff0c;然后让你判断能不能通过这种操…

迷宫2 ——单调队列解决bfs问题

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15196 来源&#xff1a;牛客网 题目描述 这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M&#xff0c;左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。每一格都用-…

D. 505

传送门 分析 这个道题的题意是给你一个n * m的01矩阵&#xff0c;然后可以更改矩阵中的数字&#xff0c;比如把0改成1&#xff0c;或者把1改成0&#xff0c;要求最后矩阵中没有任何一个边长为偶数的子矩阵中含有偶数个1&#xff0c;如果不含偶数边长的子矩阵&#xff0c;则不…

Fluctuation Limit 构造

链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6860. 来源&#xff1a;杭电多校第八场 题目描述 给你n个范围[li,ri]和一个整数x&#xff0c;要求构建一个长度为n的数组ai&#xff0c;要求保证ai > li && ai < ri,并且保证相邻两个x之间的差值的…