NEUQ-ACM预备队训练-week8（背包）-创新互联

T1.P1616 疯狂的采药

洛谷原题

创新互联是一家集网站建设,滦州企业网站建设,滦州品牌网站建设,网站定制,滦州网站建设报价,网络营销,网络优化,滦州网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

1. 每种草药可以无限制地疯狂采摘。

2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第 2 到第 (m + 1) 行，每行两个整数，第 (i + 1) 行的整数 a_i, b_i​ 分别表示采摘第 i 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的大总价值。

输入输出样例

输入

70 3
71 100
69 1
1 2

输出

140

说明/提示

数据规模与约定

• 对于 30% 的数据，保证 m≤1000 。
• 对于 100% 的数据，

也是背包问题，不过是完全背包问题，每种东西我们可以取无数个，当然还是需要滚动数组来解，不过和普通背包不一样的地方是，普通背包滚动的时候是从后往前，为了保证一个东西只取一次，完全背包我们需要从前往后，也就是不管取了几次，只需要让总和大就行，代码方面其实只需要把for循环里的条件改一下就可以

#includeusing namespace std;
long long bag[10000005];
int  t, m, daxiao[10005], value[10005];

int main() {
	cin >>t >>m;
	for (int i = 1; i<= m; i++) {
		cin >>daxiao[i] >>value[i];
	}
	for (int i = 1; i<= m; i++) {
		for (int j = daxiao[i]; j<= t; j += daxiao[i]) {
			bag[j] = max(bag[j], bag[j - daxiao[i]] + value[i]);
		}
	}
	cout<< bag[t];
	return 0;
}

T2.P1833 樱花

洛谷原题

题目描述

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

输入格式

共 n+1行：

第 1 行：现在时间 Ts​（几时：几分），去上学的时间 Te​（几时：几分），爱与愁大神院子里有几棵樱花树 n。这里的 Ts​，Te​ 格式为：hh:mm，其中 0≤hh≤23，0≤mm≤59，且 hh,mm,n 均为正整数。

第 2 行到第 n+1 行，每行三个正整数：看完第 i 棵树的耗费时间 Ti​，第 i 棵树的美学值 Ci​，看第 i 棵树的次数 Pi​（Pi​=0 表示无数次，Pi​ 是其他数字表示最多可看的次数）。

输出格式

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

输入输出样例

输入

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出

11

说明/提示

100% 数据：Te​−Ts​≤1000（即开始时间距离结束时间不超过 1000 分钟），n≤10000。保证 Te​,Ts​ 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 2 次。

还是背包问题，把看樱花的时间合理安排在一个时间段内，可以把看樱花消耗的时间看成重量，总共的时间看成背包容量，然后往背包里塞樱花（bushi），因为题目保证是同一天的时间所以直接用scanf读入然后计算一下就可以得到背包容量，且这个容量是小于1000的，还有一点是它每棵樱花可以看的次数不同，也就是混合背包问题，对于只看一次的，当成普通背包看待，看无数次的当成完全背包看待，看特定次数的我们可以把它拆成几个，然后当普通背包一个一个塞，例如看四次的樱花可以拆成四个看一次的樱花，然后遍历四次就可以，不过这样的话时间复杂度明显是很高的，所以我们需要稍微优化一下，优化方式就是二进制拆分了，例如4可以拆成1、2、1，12可以拆成1、2、4、5，这样拆分的数字可以通过特定的组合来表示任何一个小于原数的数字，然后进行普通背包的遍历就可以，优化后的算法不会超时并且成功AC

#includeusing namespace std;

int bag[1005] = {0};

inline void a(int T, int C, int t) {
	for (int i = t; i >= T; i--) {
		bag[i] = max(bag[i], bag[i - T] + C);
	}
}

int main() {
	int t1, m1, t2, m2, t, m;
	int T, C, A;
	scanf("%d:%d %d:%d", &t1, &m1, &t2, &m2);
	t = t2 * 60 + m2 - t1 * 60 - m1;
	cin >>m;
	int temp = 1;
	for (int i = 0; i< m; i++) {
		cin >>T >>C >>A;
		if (A == 0) {
			for (int j = T; j<= t; j++)
				bag[j] = max(bag[j], bag[j - T] + C);
		} else {
			while (A >temp) {
				a(T * temp, C * temp, t);
				A -= temp;
				temp *= 2;
			}
			a(T * A, C * A, t);
			temp = 1;
		}
	}
	cout<< bag[t];
	return 0;
}

T3.P1077 [NOIP2012 普及组] 摆花

洛谷原题

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai​ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 n 和 m，中间用一个空格隔开。

第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1​,a2​,⋯,an​。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 10^6+7 取模的结果。

输入输出样例

输入

2 4
3 2

输出

2

说明/提示

【数据范围】

对于20% 数据，有 0

对于 50% 数据，有 0

对于 100% 数据，有 0

作为一道动态规划题，这题乍一看可能不知道该怎么写，不过我们还是从头开始考虑，开辟一个二维数组，设f[n][k]表示前n个数的和为k的方案总数，而如果第n个数大值为2，我们很容易知道f[n][k]其实等于f[n-1][k-1]+f[n-1][k-2]，这动态转移方程不就有了，再进一步的，给他弄成滚动数组，优化空间复杂度，AC代码就出现了，附上

#includeusing namespace std;

int main() {
	int bag[105] = {1};
	int n, m, k;
	cin >>n >>m;
	for (int i = 0; i< n; i++) {
		cin >>k;
		for (int j = m; j >0; j--) {
			for (int l = 1; l<= k; l++) {
				if (j - l< 0)
					break;
				bag[j] = (bag[j] + bag[j - l]) % 1000007;
			}
		}
	}
	cout<< bag[m]<< endl;
	return 0;
}

T4.P1064 [NOIP2006 提高组] 金明的预算方案

洛谷原题

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 n 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 n 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 n 元的前提下，使每件物品的价格与重要度的乘积的总和大。

设第 j 件物品的价格为 vj​，重要度为wj​，共选中了 k 件物品，编号依次为 j1​,j2​,…,jk​，则所求的总和为：

vj1​​×wj1​​+vj2​​×wj2​​+⋯+vjk​​×wjk​​。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数 n 和希望购买的物品个数 m。

第 2 到第 (m + 1) 行，每行三个整数，第 (i + 1) 行的整数 vi​，pi​，qi​ 分别表示第 i 件物品的价格、重要度以及它对应的的主件。如果 qi​=0，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出

2200

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n≤3.2×10^4，1≤m≤60，0≤vi​≤10^4，1≤pi​≤5，0≤qi​≤m，答案不超过 2×10^5。

这个题跟一般的背包不一样的是，一般的背包是两种情况，不装和装，但是这个是五种情况

1.不买

2.只买主件

3.买主件和第一个附件

4.买主件和第二个附件

5.买主件和两个附件

所以如果用背包的方式来求解，应该是在五种情况下取大值，同时这道题还有一个很容易丢分的地方是，它主件是按照行数给的，不是按照主件出现的顺序，之后我们用背包来求解就可以了，代码如下

#includeusing namespace std;

int main() {
	int zhongliang[4][65] = {0};
	int jz[4][65] = {0};
	int bag[32005] = {0};
	int n, m;
	cin >>n >>m;
	int jiazhi, zhongyao, zhujian;
	for (int i = 1; i<= m; i++) {
		cin >>jiazhi >>zhongyao >>zhujian;
		if (zhujian) {
			if (zhongliang[1][zhujian]) {
				zhongliang[2][zhujian] = zhongliang[0][zhujian] + jiazhi;
				jz[2][zhujian] = jz[0][zhujian] + jiazhi * zhongyao;
				zhongliang[3][zhujian] = zhongliang[1][zhujian] + jiazhi;
				jz[3][zhujian] = jz[1][zhujian] + jiazhi * zhongyao;
			} else {
				zhongliang[1][zhujian] = zhongliang[0][zhujian] + jiazhi;
				jz[1][zhujian] = jz[0][zhujian] + jiazhi * zhongyao;
			}
		} else {
			zhongliang[0][i] = jiazhi;
			jz[0][i] = jiazhi * zhongyao;
		}
	}
//	for (int i = 1; i<= m; i++) {
//		cout<< zhongliang[0][i]<< ' '<< zhongliang[1][i]<< ' '<< zhongliang[2][i]<< ' '<< zhongliang[3][i]<< endl;
//	}
//	for (int i = 1; i<= m; i++) {
//		cout<< jz[0][i]<< ' '<< jz[1][i]<< ' '<< jz[2][i]<< ' '<< jz[3][i]<< endl;
//	}
	for (int i = 1; i<= m; i++) {
		if (!zhongliang[0][i])
			continue;
		for (int j = n; j >= 0; j--) {
			if (j >= zhongliang[0][i]) {
				bag[j] = max(bag[j], bag[j - zhongliang[0][i]] + jz[0][i]);
			}
			if (j >= zhongliang[1][i]) {
				bag[j] = max(bag[j], bag[j - zhongliang[1][i]] + jz[1][i]);
			}
			if (j >= zhongliang[2][i]) {
				bag[j] = max(bag[j], bag[j - zhongliang[2][i]] + jz[2][i]);
			}
			if (j >= zhongliang[3][i]) {
				bag[j] = max(bag[j], bag[j - zhongliang[3][i]] + jz[3][i]);
			}
		}
	}
	cout<< bag[n]<< endl;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：NEUQ-ACM预备队训练-week8（背包）-创新互联
文章位置：http://dzwzjz.com/article/dcppds.html