USACO中的背包问题（TEXT）题目列表题目简解

USACO是USA的缩写，在世界各地举办许多计算机比赛。

USACO是一个非常适合初学者的题库。 我觉得它的特点是题目质量高，循序渐进，文字和问题分析都很好。 关于背包问题的文字（TEXT）也值得一读。

此外，USACO是USACO全年举办的全球性系列赛事。 这里也推荐NOIP玩家参与。

我整理了一些 USACO 涉及背包问题的问题，这应该是很好的练习。 其中带加号的是我比较推荐的，带感叹号的是我认为对NOIP玩家来说比较有挑战性的。

问题列表，问题简单解释

以下文字摘自我写的文章《USACO经验》。 这篇文章的完整版本，包括我的程序，可以在 DD 的 USACO 中找到。

是一个加权01背包问题，也就是说：每种类型只有一件物品，只能选择放或不放； 每个物品都有相应的重量，目标是最大化或最小化总重量。 其最简单的状态转移方程为：f[k][i] = max{f[k-1][i] , f[k-1][iv[k]]+w[k]}。 f[k][i]表示在前k个物品上花费成本i可以获得的最大权重。 v[k]和w[k]分别是第k个物品的成本和重量。 可见f[k]的求解过程就是利用第k项更新f[k-1]的过程。 事实上，没有必要使用二维数组。 只需要定义f[i]，然后对于每一项k，依次检查f[i]和f[iv[k]]+w[k]的大小。 如果后者较大，则更新前者。 这是背包问题中典型的优化方法。

问题中，对于每件物品的使用量没有直接的限制，但是对于使用的物品总量有限制。 求第一个不能由这有限数量的物品组成的背包的尺寸。 （可以等价地考虑）令f[k][i]表示用前k个物品组成一个大小为i的背包所需的最少物品数。 那么f[k][i]= min{f[k-1][i],f[k-1][ij*s[k]]+j}，其中j是选择的第k个项目的数量使用时，可以使用与上述相同的方法将该方程处理为一维。 求解时，首先设定一个粗略的循环上限，即最大项乘以最大项数。

金钱是一个多背包问题。 也就是说，每个项目都可以无限次使用。 需要解决的是构成一种背包的不同解决方案的总数。 基本上，只需将一般多背包方程中的 min 改为 sum 即可。

该型号也是一款多功能背包。 需要找到给定物品无法放入的背包尺寸的最大值（可能不存在）。 我们只需要根据定理“如果 i 和 j 互质，则关于 x 和 y 的不定方程 i*x+y*j=n 一定有正整数解，其中 n >i*j”。 子集和问题相当于当物品大小为前 N 个自然数时，求大小为 N*(N+1)/4 的 01 背包的选项数量。

可以用解决背包问题的思路来设计解决方案。 我的状态转移方程如下： f[i][j][t]=max{f[i][j][t-1] , f[i-1][j][t] , f[i - 1][j][t-时间[i]]+1 , f[i-1][j-1][T]+(t>=时间[i])}。 其中，f[i][j][t]表示使用j张完整的光盘和录制了t分钟的光盘，可以放入第i首歌曲的最大歌曲数。 T是光盘的最大容量，t>=time[i]是一个bool值转换成int，值为0或1。但是我后来发现我当时设计的状态和方程效率有点低。 如果改成这样：f[i][j]=(a,b)则意味着在前i首歌曲中选择j需要使用一张完整的CD。 而一张盘记录了b分钟，会大大降低时间和空间复杂度。 这种将状态值变成二维的方法值得注意。

Milk4 是这些背包问题中最难的。 很多人无法用纯DP方法来解决。 相反，他们使用迭代加深来搜索枚举中使用的桶，将其转换为多背包问题，然后进行DP。 由于USACO的数据较弱，迭代加深的深度很小，因此可以实现AC，但我们仍然可以使用纯DP方法完美解决。 令 f[k] 为称出 k 单位牛奶所需的最少桶数。 然后就可以用类似于多个背包的方法，反复更新f数组，找到最小值。 然而，困难在于如何输出字典序最小的解。 我们可以记录每个i的pre_f[i]和pre_v[i]。 获得i单位牛奶的过程是用pre_f[i]单位牛奶加上编号为pre_v[i]的几个桶的牛奶。 这样就可以逐步得到获得i单位牛奶的完整解。 为了最小化计划的字典顺序，每次我们找到具有相同桶数的计划时，我们都会将存储的计划与新计划进行比较，然后决定是否更新该计划。 为了使比较更快，使用不同大小的存储桶对 f 数组的更新首先变大，然后变小。 USACO官方的解决方案正是这个想法。 如果你觉得上面的文字难以理解，可以阅读官方的程序或者我的程序。