`

P10: USACO中的背包问题

 
阅读更多

附:USACO中的背包问题

USACO是USA Computing Olympiad的简称,它组织了很多面向全球的计算机竞赛活动。

USACO Trainng是一个很适合初学者的题库,我认为它的特色是题目质量高,循序渐进,还配有不错的课文和题目分析。其中关于背包问题的那篇课文 (TEXT Knapsack Problems) 也值得一看。

另外,USACO Contest是USACO常年组织的面向全球的竞赛系列,在此也推荐NOIP选手参加。

我整理了USACO Training中涉及背包问题的题目,应该可以作为不错的习题。其中标加号的是我比较推荐的,标叹号的是我认为对NOIP选手比较有挑战性的。

题目列表

  • Inflate (+) (基本01背包)
  • Stamps (+)(!) (对初学者有一定挑战性)
  • Money
  • Nuggets
  • Subsets
  • Rockers (+) (另一类有趣的“二维”背包问题)
  • Milk4 (!) (很怪的背包问题问法,较难用纯DP求解)

题目简解

以下文字来自我所撰的《USACO心得》一文,该文的完整版本,包括我的程序,可在DD的USACO征程中找到。

Inflate 是加权01 背包问题,也就是说:每种物品只有一件,只可以选择放或者 不放;而且每种物品有对应的权值,目标是使总权值最大或最小。它最朴素的状态转移方程是:f[k][i] = max{f[k-1][i] , f[k-1][i-v[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[i-v[k]]+w[k]的大小,如果后者更大,就对前者进行更新。这是背包问题中典型的优化方法。

题目stamps 中,每种物品的使用量没有直接限制,但使用物品的总量有限制。 求第一个不能用这有限个物品组成的背包的大小。(可以这样等价地认为)设f[k][i] 表示前k 件物品组成大小为i 的背包, 最少需要物品的数量。则f[k][i]= min{f[k-1][i],f[k-1][i-j*s[k]]+j},其中j 是选择使用第k 件物品的数目,这个方程运用时 可以用和上面一样的方法处理成一维的。求解时先设置一个粗糙的循环上限,即最 大的物品乘最多物品数。

Money 是多重背包问题。也就是每个物品可以使用无限多次。要求解的是构成 一种背包的不同方案总数。基本上就是把一般的多重背包的方程中的min 改成sum 就行了。

Nuggets 的模型也是多重背包。要求求解所给的物品不能恰好放入的背包大小 的最大值(可能不存在)。只需要根据“若i、j 互质,则关于x、y 的不定方程i*x+y*j=n 必有正整数解,其中n>i*j”这一定理得出一个循环的上限。 Subsets 子集和问题相当于物品大小是前N 个自然数时求大小为N*(N+1)/4 的 01 背包的方案数。

Rockers 可以利用求解背包问题的思想设计解法。我的状态转移方程如下: f[i][j][t]=max{f[i][j][t-1] , f[i-1][j][t] , f[i-1][j][t-time[i]]+1 , f[i-1][j-1][T]+(t>=time[i])}。其中 f[i][j][t]表示前i 首歌用j 张完整的盘和一张录了t 分钟的盘可以放入的最多歌数,T 是 一张光盘的最大容量,t>=time[i]是一个bool 值转换成int 取值为0 或1。但我后来发 现我当时设计的状态和方程效率有点低,如果换成这样:f[i][j]=(a,b)表示前i 首歌中 选了j 首需要用到a 张完整的光盘以及一张录了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 的官 方题解正是这一思路。如果认为以上文字比较难理解可以阅读官方程序或我的程序。

分享到:
评论

相关推荐

    背包问题九讲(讲述经典的背包问题)

    USACO 中的背包问题是指在 USACO 比赛中的背包问题,这些问题都可以用动态规划来解决,状态转移方程与基本的背包问题相同,但需要考虑具体的问题描述和约束条件。 背包问题是一种非常重要和有用的计算机科学问题,...

    背包问题9讲

    附录中提及的内容为:USACO中的背包问题,即美国计算机奥林匹克竞赛(USACO)网站上可以找到的背包问题练习题和简单解答;背包问题的搜索解法,指的是在动态规划之外,探索使用其他算法(如搜索算法)来解决背包问题...

    usaco:USACO培训门户网站问题的解决方案

    【标题】USACO:USACO培训门户网站问题的解决方案 【内容】 USACO,全称为United States of America Computing Olympiad,是一项针对美国中学生设立的计算机编程竞赛,旨在提高学生的算法设计和编程能力。USACO...

    USACO-Practice:USACO 实践

    字符串操作经常出现在USACO的问题中,理解这些算法可以帮助解决字符串相关问题。 4. **数学应用**:组合数学(排列组合、鸽巢原理等)、数论(模运算、欧几里得算法求最大公约数、扩展欧几里得算法求逆元)和几何...

    背包问题的各种算法实现

    目录 第一讲 01背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组的背包问题 ...附录一:USACO中的背包问题 附录二:背包问题的搜索解法

    背包问题九讲

    "背包问题九讲" 本资源为一系列关于背包问题的讲解,共九讲,涵盖了大部分背包问题的理论基础。通过这九讲,读者可以系统地学习背包问题的基本概念、解决方法...USACO 中的背包问题提供了一个列表,供读者练习和学习。

    USACO_Training:USACO_培训

    而`Gift1.java`则可能与礼物分配、背包问题或搜索算法有关,需要掌握数组操作、递归或回溯法。 在USACO的Java培训中,学习者会接触到以下关键知识点: 1. **基础语法**:变量声明、条件语句(if-else)、循环(for...

    背包九讲问题

    #### 附录一:USACO中的背包问题 - **定义**:USACO是美国计算机奥林匹克竞赛,其中包含了大量的背包问题供选手练习。 - **解决方法**:通过分析这些背包问题的特点和解题技巧,可以更好地理解和掌握背包问题的各种...

    信息学奥赛背包问题九讲

    【信息学奥赛背包问题九讲】是一篇深入探讨动态规划中背包问题的教程,旨在帮助参赛者理解和解决这类问题。教程分为九个主要部分,覆盖了从基础到进阶的各种背包问题类型,并有两个附录专门讨论USACO中的背包问题和...

    usaco_solutions:usaco解决方案

    本压缩包"usaco_solutions"中的内容,显然是对历年来USACO比赛题目解答的集合,对于学习和理解C++编程以及算法应用具有极高的参考价值。 首先,让我们深入探讨C++语言本身。C++是一种静态类型的、编译式的、通用的...

    USACO:USACO

    【USACO:美国计算机奥赛详解】 USACO,全称为USA Computing Olympiad,是一项针对高中生的在线编程竞赛,旨在提升参赛者在算法、数据结构以及问题解决方面的能力。USACO通常由基础、银牌、金牌和白金四个级别组成...

    背包问题九讲(免费获取)

    **附:USACO中的背包问题** 列出USACO训练平台上的背包问题实例,提供解题思路,供练习者参考。 在学习这些背包问题时,重要的是进行深入思考,因为动态规划的关键在于理解和构建状态转移方程,而不仅仅是记住公式...

    背包九讲PDF格式。

    dd_engi 的背包九讲 目录 第一讲 01背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 ...附:USACO中的背包问题

    背包九讲完整版c++

    背包九讲完整版c++ 第一讲01背包问题 第二讲完全背包问题 第三讲多重背包问题 第四讲混合三种背包问题 第五讲二维费用的背包问题 第六讲分组的背包问题 第七讲有依赖的背包问题 ...附: USACO中的背包问题

    USACO 1.1 c++源程序

    2. **数组与字符串操作**:在USACO中,数组常用于处理序列数据,字符串则涉及文本处理问题,如查找、替换和比较。 3. **指针**:理解指针是C++的关键,它们允许直接操作内存,实现动态数据结构和高效算法。 4. **...

    背包九讲完整版

    #### USACO中的背包问题 - **应用场景**:USACO训练平台提供了大量的背包问题供练习,这些题目涵盖了从基础到进阶的各种背包问题。 - **解决方法**:通过实践,熟悉并掌握不同类型背包问题的解决策略,提升解决问题...

    usaco心得及总结

    - **方法**: 将一般的多重背包问题方程中的 `min` 改为 `sum`。 **Nuggets** - **问题**: 找出所有不能恰好放入的背包大小的最大值。 - **方法**: 利用数学原理确定循环上限。 **Subsets(子集和问题)** - **问题...

    C-Usaco-Work:Usaco在C中的工作

    "Usaco在C中的工作"意味着该项目可能包含了使用C语言编写Usaco问题解决方案的过程。这可能包括一系列的练习题、代码示例、解题策略以及对C语言特性的深入讲解,帮助学生熟悉如何利用C语言来解决复杂的算法问题。 ...

    usaco的程序,共20道左右,验证通过

    3. **动态规划**:第一章可能会引入动态规划的基本概念,如背包问题、最长公共子序列、最短路径等。动态规划能有效地解决一些具有重叠子问题和最优子结构的问题。 4. **贪心算法**:在USACO的初期阶段,贪心算法也...

    USACO全部题目官方分析翻译

    在USACO题目中,动态规划的运用可以解决背包问题、最长公共子序列等问题。 3. **数据结构**:二叉树、平衡树(AVL、红黑树)、图、队列、栈等数据结构的运用也是竞赛的重点。例如,二叉查找树在快速查找和插入中起...

Global site tag (gtag.js) - Google Analytics