背包

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

错误贪心

经典错误做法：
先选价值高的
先选体积小的
先选价值/体积大的
先选价值-体积大的

对于背包问题，几乎所有贪心都是错误的，常见错误做法

优先选价值大的
优先选体积小的
优先选价值/体积比例大的

基本思路

用f[i][j]表示前i个物品中取j的重量，的最大价值。
其中第一位可以用滚动数组优化。

零一背包

每个物品只能取或不取。
对于一个重量为x价值为y的物品，转移方程为
f[i][j] = max(f[i][j], f[i-1][j-x]+y);
然后i维可以用滚动数组，或者是倒序循环优化掉。
比如采药

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[1020];
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = m; j >= x; j--) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

完全背包

每个物品可以取任意多次
对于一个重量为x价值为y的物品，转移方程为
f[i][j] = max(f[i][j], f[i][j-x]+y);
然后i维可以用滚动数组，或者是正序循环优化掉。
比如疯狂的采药

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[100020];
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = x; j <= m; j++) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

多重背包

每个物品可以选的次数大于 $1$ ，但上限不是无限大，而要求小于等于 $c$ 。
一个显而易见的暴力做法是直接拆成 $c$ 个物品做零一背包。
主要有两种做法，二进制拆分，和单调队列。
第一种做法是不拆成大小为 $1$ 的物品了，拆成大小为
$1, 2, 4, 8, \ldots, c - 2^k + 1$
的物品，其中 $k$ 是满足 $c - 2^k + 1 > 0$ 最大的 $k$ 。

另一种是单调队列，相当于f[i] = max(f[i - j * x] + j * y)
其中j满足0 <= j <= c。
如果把数组的每x个取出的话，相当于是区间最值。

knapsack problem

01 knapsack
for (size downto 0)
infinite knapsack
for (0 to size)
finite knapsack
2 solutions
binary 二进制拆分

100 item, weight w, value v
we can do 100 times 01 knapsack

void update(int w, int v)
{
for (int j = totalsize; j >= w; j--)
{
f[j] = max(f[j], f[j - w] + v);
}
}

for (int k = 0; k < 100; k++)
{
update(w, v);
}
too slow

100 = 1 + 2 + 4 + 8 + 16 + 32 + 37

50 = 2 + 16 + 32
50 = 1 + 4 + 8 + 37

update(w * 1, v * 1);
update(w * 2, v * 2);
update(w * 4, v * 4);
update(w * 8, v * 8);
update(w * 16, v * 16);
update(w * 32, v * 32);
update(w * 37, v * 37);

limit = 100;
for (int k = 1; k <= limit; k *= 2)
{
update(w * k, v * k);
limit -= k;
}
update(w * limit, v * limit);

背包统计方案数

一些情况下，物品并没有价值，而是希望计算方案数。
对于零一背包和完全背包，几乎一样。
对于有限背包，就不能拆成零一背包来做了。
而需要下面这个题目的技巧
51nod 1597

一个经典的例子是通过完全背包计算Partition numbers

#include <bits/stdc++.h>
using namespace std;
int n, p = 1000000007;
int f[100020];
int main() {
	cin >> n;
	f[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			f[j] = (f[j] + f[j - i]) % p;
		}
	}
	cout << f[n] << endl;
	return 0;
}

时间复杂度是 $O(n^2)$ 的，虽然有利用五边形数公式优化到 $O(n\sqrt{n})$ 的做法。

bitset 优化 01 背包

bitset 无法优化完全背包
一些背包题，如果只关注每个值能否得到，或者是得到每个值的方案数的奇偶性。
可以使用bitset优化。

只关注每个值能否得到
atcoder agc020_c
需要知道每个值的方案数的奇偶性的题目：
bzoj 3687

if infinite times
change for (int j = x; j <= m; j++)

Fibonacci Number
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 2 + 1
4 = 2 + 1 + 1
4 = 2 + 2

https://en.wikipedia.org/wiki/Partition_(number_theory)

memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
f[j] += f[j - i];
}
}

时间复杂度

NP-complete

时间复杂度和背包大小有关

退背包

计数

最优化（分治）

参考题目

P1048 [NOIP2005 普及组] 采药

https://www.luogu.com.cn/problem/P1048

题目描述

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

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

输入格式

第一行有 $2$ 个整数 $T$ （ $1 \le T \le 1000$ ）和 $M$ （ $1 \le M \le 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 $30\%$ 的数据， $M \le 10$ ；
对于全部的数据， $M \le 100$ 。

【题目来源】

NOIP 2005 普及组第三题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[1020];
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = m; j >= x; j--) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

题解

最优化 01背包

f[i][j] 表示前i个物品，j的体积，最大价值是多少
f[i][j] first i items, use j volume, what is the max value?
f[i][j] = max(f[i-1][j], f[i-1][j-x[i]] + y[i])

f[i] = max(f[i], f[i - x] + y)
零一背包倒序（每个物品至多1次）
完全背包正序（每个物品任意多次）

本题中不需要用完所有的体积
如果要求必须用完所有的体积
那么把 f 清成负无穷，f[0] = 0
memset(f, 0xc0, sizeof f);
f[0] = 0

P1616 疯狂的采药

https://www.luogu.com.cn/problem/P1616

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

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

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

此题和原题的不同点：

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$ ， $1 \leq t \leq 10^7$ ，且 $1 \leq m \times t \leq 10^7$ ， $1 \leq a_i, b_i \leq 10^4$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f[10000020];
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = x; j <= m; j++) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%lld\n", f[m]);
	return 0;
}

题解

最优化完全背包

P1164 小A点菜

https://www.luogu.com.cn/problem/P1164

题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$ 。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$ ，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$ 。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待 $1$ 秒。

输入格式

第一行是两个数字，表示 $N$ 和 $M$ 。

第二行起 $N$ 个正数 $a_i$ （可以有相同的数字，每个数字均在 $1000$ 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 $int$ 之内。

样例 #1

样例输入 #1

4 4
1 1 2 2

样例输出 #1

提示

2020.8.29，增添一组 hack 数据 by @yummy

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[100020];
int main() {
	scanf("%d%d", &n, &m);
	f[0] = 1;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		for (int j = m; j >= x; j--) {
			f[j] += f[j - x];
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

题解

01背包
计数

P1832 A+B Problem（再升级）

https://www.luogu.com.cn/problem/P1832

题目背景

·题目名称是吸引你点进来的

·实际上该题还是很水的

题目描述

·1+1=? 显然是2

·a+b=? 1001回看不谢

·哥德巴赫猜想似乎已呈泛滥趋势

·以上纯属个人吐槽

·给定一个正整数n，求将其分解成若干个素数之和的方案总数。

输入格式

一行：一个正整数n

输出格式

一行：一个整数表示方案总数

样例 #1

样例输入 #1

样例输出 #1

提示

【样例解释】

7=7
7=2+5

7=2+2+3

【福利数据】

【输入】 20

【输出】 26

【数据范围及约定】

对于30%的数据 1<=n<=10

对于100%的数据，1<=n<=10^3

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
long long f[1020];
bool Prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}
int main() {
	cin >> n;
	f[0] = 1;
	for (int i = 2; i <= n; i++) {
		if (Prime(i)) {
			for (int j = i; j <= n; j++) {
				f[j] += f[j - i];
			}
		}
	}
	cout << f[n] << endl;
	return 0;
}

题解

P1734 最大约数和

https://www.luogu.com.cn/problem/P1734

题目描述

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S。

输出格式

输出最大的约数之和。

样例 #1

样例输入 #1

样例输出 #1

提示

样例说明

取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

数据规模

S<=1000

参考代码

#include <bits/stdc++.h>
using namespace std;
int s, f[1020];
int main() {
	scanf("%d", &s);
	for (int i = 1; i <= s; i++) {
		int v = 0;
		for (int j = 1; j < i; j++) {
			if (i % j == 0) {
				v += j;
			}
		}
		for (int j = s; j >= i; j--) {
			f[j] = max(f[j], f[j - i] + v);
		}
	}
	printf("%d\n", f[s]);
	return 0;
}

题解

P2871 [USACO07DEC]Charm Bracelet S

https://www.luogu.com.cn/problem/P2871

题目描述

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$ ，价值是 $D_i$ 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

第一行：物品个数 $N$ 和背包大小 $M$ 。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$ 。

输出格式

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

输出一行最大价值。

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[20020];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = m; j >= x; j--) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

题解

最优化零一背包
最优化 01背包

P2639 [USACO09OCT]Bessie's Weight Problem G

https://www.luogu.com.cn/problem/P2639

题目描述

Bessie像她的诸多姊妹一样，因为从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置于一个及其严格的节食计划之中。她每天不能吃多过H (5 <= H <= 45,000)公斤的干草。 Bessie只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N (1 <= N <= 500)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。给定一个列表表示每捆干草的重量S_i (1 <= S_i <= H), 求Bessie不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

输入格式

* 第一行: 两个由空格隔开的整数: H 和 N * 第2到第N+1行: 第i+1行是一个单独的整数，表示第i捆干草的重量S_i。

输出格式

* 第一行: 一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的干草。

样例 #1

样例输入 #1

样例输出 #1

提示

输入说明:

有四捆草，重量分别是15, 19, 20和21。Bessie在56公斤的限制范围内想要吃多少就可以吃多少。

输出说明:

Bessie可以吃3捆干草（重量分别为15, 20, 21）。恰好达到她的56公斤的限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
bitset<100000> f;
int main() {
	f[0] = true;
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		f |= f << x;
	}
	for (int i = m; i >= 0; i--) {
		if (f[i]) {
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

题解

只关注方案数是否为0的零一背包，可以用 bitset 优化

P5020 [NOIP2018 提高组] 货币系统

https://www.luogu.com.cn/problem/P5020

题目背景

NOIP2018 提高组 D1T2

题目描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$ ，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 $n$ 、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$ 。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$ ，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] \times t[i]$ 的和为 $x$ 。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3$ , $a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$ ，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$ ，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$ 。

输入格式

输入文件的第一行包含一个整数 $T$ ，表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。每组数据的第一行包含一个正整数 $n$ 。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$ 。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$ 。

样例 #1

样例输入 #1

2 
4 
3 19 10 6 
5 
11 29 13 19 17

样例输出 #1

2   
5

提示

在第一组数据中，货币系统 $(2, [3,10])$ 和给出的货币系统 $(n, a)$ 等价，并可以验证不存在 $m < 2$ 的等价的货币系统，因此答案为 $2$ 。在第二组数据中，可以验证不存在 $m < n$ 的等价的货币系统，因此答案为 $5$ 。

【数据范围与约定】

对于 $100\%$ 的数据，满足 $1 ≤ T ≤ 20, n,a[i] ≥ 1$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[25020];
int a[120];
int t, n;
int main() {
	scanf("%d", &t);
	for (int tt = 0; tt < t; tt++) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		sort(a, a + n);
		memset(f, 0, sizeof f);
		f[0] = 1;
		int z = 0;
		for (int i = 0; i < n; i++) {
			if (f[a[i]] == 0) {
				z++;
				for (int j = a[i]; j <= a[n - 1]; j++) {
					f[j] |= f[j - a[i]];
				}
			}
		}
		printf("%d\n", z);
	}
	return 0;
}

题解

只需要知道每个金额能否被表示出/被表示出的次数是否大于等于2。
计数完全背包只关注是否可行

https://henryhuang.blog.luogu.org/solution-p5020
另一种思路
直接对所有面值做背包

记录 min(方案数, 2)
记录每个金额至多用多少个面值，如果对一个面值，可以用多张表示出自己，那么自己就是没必要的

P1510 精卫填海

https://www.luogu.com.cn/problem/P1510

题目描述

【版权说明】

本题为改编题。

【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。

输入格式

输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

样例 #1

样例输入 #1

100 2 10
50 5
50 5

样例输出 #1

样例 #2

样例输入 #2

10 2 1
50 5
10 2

样例输出 #2

Impossible

提示

【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y;
int f[10020];
int main()
{
	cin >> m >> n >> c;
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;
		for (int j = m; j >= 0; j--)
		{
			f[j] = min(f[j], f[max(j - x, 0)] + y);
		}
	}
	if (f[m] <= c)
	{
		cout << c - f[m] << endl;
	}
	else
	{
		cout << "Impossible" << endl;
	}
	return 0;
}

题解

最优化 01背包

2种做法
对于每个体积，算出最小的体力
对于每个体力，算出最大的体积

P1855 榨取kkksc03

https://www.luogu.com.cn/problem/P1855

题目描述

洛谷 2 的团队功能是其他任何 OJ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 OJ 并高效率的完成训练计划。

为什么说是搭建 OJ 呢？为什么高效呢？

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 OI 赛制还可以是 ICPC 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“x 校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。

kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

输入格式

第一行三个整数 $n,M,T$ ，表示一共有 $n$ （ $1 \le n \le 100$ ）个愿望， kkksc03 的手上还剩 $M$ （ $0 \le M \le 200$ ）元，他的暑假有 $T$ （ $0 \le T \le 200$ ）分钟时间。

第 $2$ ~ $n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。

输出格式

一行，一个数，表示 kkksc03 最多可以实现愿望的个数。

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[220][220]; // i的金钱, j的时间  i的金钱，j个任务，最小的时间
int n, m, t, x, y;
int main() {
	cin >> n >> m >> t;
	memset(f, 0x3f, sizeof f);
	for (int i = 0; i <= m; i++) {
		f[i][0] = 0;
	}
	for (int k = 0; k < n; k++) {
		cin >> x >> y;
		for (int i = m; i >= x; i--) {
			for (int j = n; j >= 1; j--) {
				f[i][j] = min(f[i][j], f[i - x][j - 1] + y);
			}
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		if (f[m][i] > t) {
			printf("%d\n", i - 1);
			break;
		}
	}
}

题解

P1910 L国的战斗之间谍

https://www.luogu.com.cn/problem/P1910

题目背景

L国即将与I国发动战争！！

题目描述

俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？

输入格式

N M X

A1 B1 C1

A2 B2 C2

………………

AN BN CN

输出格式

能得到的资料总数

样例 #1

样例输入 #1

样例输出 #1

提示

数据范围：

1≤n≤100,1≤m≤1000, 1≤x≤1000

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1020][1020];
int n, m, x, a, b, c;
int main()
{
	scanf("%d%d%d", &n, &m, &x);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		for (int j = m; j >= b; j--)
		{
			for (int k = x; k >= c; k--)
			{
				f[j][k] = max(f[j][k], f[j - b][k - c] + a);
			}
		}
	}
	printf("%d\n", f[m][x]);
	return 0;
}

题解

P1757 通天之分组背包

https://www.luogu.com.cn/problem/P1757

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$ ，表示一共有 $n$ 件物品，总重量为 $m$ 。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$ ，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

样例输出 #1

提示

$1 \leq m, n \leq 1000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int m, n, x, y, z;
map<int, vector<pair<int, int> > > a;
int f[1020];
int main()
{
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[z].push_back(make_pair(x, y));
	}
	for (auto i: a)
	{
		for (int j = m; j >= 0; j--)
		{
			for (pair<int, int> k: i.second)
			{
				if (j >= k.first)
				{
					f[j] = max(f[j], f[j - k.first] + k.second);
				}
			}
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

题解

P2563 [AHOI2001]质数和分解

https://www.luogu.com.cn/problem/P2563

题目描述

任何大于 $1$ 的自然数 $n$ 都可以写成若干个大于等于 $2$ 且小于等于 $n$ 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如， $9$ 的质数和表达式就有四种本质不同的形式：

$9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7$ 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 $n$ 可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数 $n(2 \leq n \leq 200)$ 。

输出格式

依次输出每一个自然数 $n$ 的本质不同的质数和表达式的数目。

样例 #1

样例输入 #1

2
200

样例输出 #1

1
9845164

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n = 200;
int v[201];
int f[201];
int main()
{
	f[0] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!v[i])
		{
			for (int j = i; j <= n; j++)
			{
				f[j] += f[j - i];
			}
			for (int j = i; j <= n; j += i)
			{
				v[j] = i;
			}
		}
	}
	while (cin >> n)
	{
		cout << f[n] << endl;
	}
	return 0;
}

题解

计数完全背包

P2918 [USACO08NOV]Buying Hay S

https://www.luogu.com.cn/problem/P2918

题目描述

Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.

约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1 \leq H \leq 50000)$ 磅干草。

他知道 $N(1 \leq N\leq 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 公司卖的干草包重量为 $P_i (1 \leq P_i \leq 5,000)$ 磅，需要的开销为 $C_i (1 \leq C_i \leq 5,000)$ 美元。每个干草公司的货源都十分充足，可以卖出无限多的干草包。

帮助约翰找到最小的开销来满足需要，即采购到至少 $H$ 磅干草。

输入格式

* Line 1: Two space-separated integers: N and H

* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i

输出格式

* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

样例 #1

样例输入 #1

2 15 
3 2 
5 3

样例输出 #1

提示

FJ can buy three packages from the second supplier for a total cost of 9.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int f[50020];
int main()
{
	cin >> n >> m;
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;
		for (int j = 0; j <= m; j++)
		{
			int k = min(j + x, m);
			f[k] = min(f[k], f[j] + y);
		}
	}
	cout << f[m] << endl;
	return 0;
}

题解

P2725 [USACO3.1]邮票 Stamps

https://www.luogu.com.cn/problem/P2725

题目描述

给一组 $n$ 枚邮票的面值集合和一个上限 $k$ —— 表示信封上能够贴 $k$ 张邮票。请求出最大的正整数 $m$ ，满足 $1$ 到 $m$ 的面值都可以用不超过 $k$ 张邮票表示出来。

输入格式

输入的第一行是两个整数，分别代表邮票上限 $k$ 和邮票面值数 $n$ 。

自第二行起，除最后一行外，每行有 $15$ 个整数 $a_i$ ，最后一行的整数个数不超过 $15$ ，共有 $n$ 个整数，第 $i$ 个整数代表第 $i$ 种邮票的面值 $a_i$ 。

输出格式

输出一行一个整数代表 $m$ 。若 $m$ 不存在请输出 $0$ 。

样例 #1

样例输入 #1

5 2
1 3

样例输出 #1

提示

样例输入输出 1 解释

有 $1$ 分和 $3$ 分的邮票；你最多可以贴 $5$ 张邮票。很容易贴出 $1$ 到 $5$ 分的邮资（用 $1$ 分邮票贴就行了），接下来的邮资也不难：

$6 = 3 + 3$ 。
$7 = 3 + 3 + 1$ 。
$8 = 3 + 3 + 1 + 1$ 。
$9 = 3 + 3 + 3$ 。
$10 = 3 + 3 + 3 + 1$ 。
$11 = 3 + 3 + 3 + 1 + 1$ 。
$12 = 3 + 3 + 3 + 3$ 。
$13 = 3 + 3 + 3 + 3 + 1$ 。

然而，使用 $5$ 枚 $1$ 分或者 $3$ 分的邮票根本不可能贴出 $14$ 分的邮资。因此，答案为 $13$ 。

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq k \leq 200$ ， $1 \leq n \leq 50$ ， $1 \leq a_i \leq 10^4$ 。

说明

题目翻译来自 NOCOW。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[2000020];
int k, n, x;
int main() {
	cin >> k >> n;
	for (int i = 1; i < 2000010; i++) {
		f[i] = k + 1;
	}
	for (int i = 0; i < n; i++) {
		cin >> x;
		for (int j = x; j < 2000010; j++) {
			f[j] = min(f[j], f[j - x] + 1);
		}
	}
	for (int i = 0; i < 2000010; i++) {
		if (f[i] > k) {
			printf("%d\n", i - 1);
			break;
		}
	}
}

题解

P1284 三角形牧场

https://www.luogu.com.cn/problem/P1284

题目描述

和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 $n$ 块木板，每块的长度 $l_i$ 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。

请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。

输入格式

第 $1$ 行：一个整数 $n$ ；

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $l_i$ 表示第 $i$ 块木板的长度。

输出格式

仅一个整数：最大牧场面积乘以 $100$ 然后舍尾的结果。如果无法构建，输出 $-1$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

样例输入输出 1 解释

$692=\text{舍尾后的}(100\times\text{三角形面积})$ ，此三角形为等边三角形，边长为 $4$ 。

数据规模与约定

对于 $100\%$ 的数据，保证 $3\le n\le40$ ， $1\le l_i\le40$ 。

参考代码

题解

P1832 A+B Problem（再升级）
计数完全背包

P1734 最大约数和
最优化 01背包

P2639 [USACO09OCT]Bessie Weight Problem G
计数 01背包只关注是否可行，可以bitset优化

P5020 货币系统
计数完全背包只关注是否可行

P1510 精卫填海
最优化 01背包

P2918 [USACO08NOV]Buying Hay S
最优化完全背包

P1853 投资的最大效益
最优化完全背包

P1757 通天之分组背包
最优化 01背包分组背包

P2663 越越的组队
最优化 01背包二维（需要记录个数）

P1855 榨取kkksc03
最优化 01背包二维

P4377 [USACO18OPEN]Talent Show G
二分，然后背包

根据个数不同

01背包
完全背包
混合背包

分组背包

{1, 2, 4, 8, 16, 32, 64}
{1, 3, 9, 27, 81}
{1, 5, 25}
{1, 7, 49}

暴力动态规划

f[i][j] 前i个物品用了j的体积

混合背包
最优化二进制拆分，单调队列

用背包计算 partition number 拆分数

bitset 优化可行性 01背包

10
5 5
6 8

输入n个数字，从中选取若干个数字，凑出m。
很困难

n <= 40, m <= 1e18 可以做
n * m <= 1e7 可以做

背包问题添加物品的顺序，不会影响答案。
有的题目需要利用这个性质。

12 = 3,4

P1048 采药
最优化 01背包

P1616 疯狂的采药
最优化完全背包

P1832 A+B Problem（再升级）
计数完全背包

P1734 最大约数和
最优化 01背包

P2871 [USACO07DEC]Charm Bracelet S
最优化 01背包

P2639 [USACO09OCT]Bessie's Weight Problem G
计数 01背包只关注是否可行，可以bitset优化

P2918 [USACO08NOV]Buying Hay S
最优化完全背包

P1853 投资的最大效益
最优化完全背包

P1757 通天之分组背包
最优化 01背包分组背包

P2663 越越的组队
最优化 01背包二维（需要记录个数）

P1855 榨取kkksc03
最优化 01背包二维

P4377 [USACO18OPEN]Talent Show G

P4544 [USACO10NOV]Buying Feed G
100 = 1 + 2 + 4 + 8 + 16 + 32 + 37

spoj WEIGHT3

spoj WEIGHT1

abc159_f Knapsack for All Segments

https://atcoder.jp/contests/abc159/tasks/abc159_f

参考代码

题解

abc057_d Maximum Average Sets

https://atcoder.jp/contests/abc057/tasks/abc057_d
输入n个数字，从中至少选A个，至多选B个，问最大平均值

参考代码

题解

直接背包（DP）
f[i][j]表示前i个物品选j个，最大的和是多少

abc169_f Knapsack for All Subsets

https://atcoder.jp/contests/abc169/tasks/abc169_f
输入 $n$ 个数字
设 $f(T)$ 表示集合 $T$ 有多少个子集，和为 $S$
对于 $n$ 个数字的所有子集 $T$ 求 $f(T)$ 之和

背包

分类

错误贪心

基本思路

零一背包

完全背包

多重背包

背包统计方案数

bitset 优化 01 背包

时间复杂度

退背包

计数

最优化（分治）

参考题目

P1048 [NOIP2005 普及组] 采药

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P1616 疯狂的采药

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P1164 小A点菜

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P1832 A+B Problem（再升级）

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P1734 最大约数和

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P2871 [USACO07DEC]Charm Bracelet S

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

题解

P2639 [USACO09OCT]Bessie's Weight Problem G

题目描述

输入格式