UVa 624 CD

📅 2026/7/4 22:41:39 👁️ 次浏览

题目描述你有一盘长度为NNN分钟的磁带以及一张CD\texttt{CD}CD上有若干首曲目每首曲目时长已知整数。你需要从CD\texttt{CD}CD中选择若干首曲目使得这些曲目的总时长不超过NNN并且尽可能接近NNN即剩余未使用的磁带空间最小。如果存在多种最优方案输出任意一种均可但需要按照曲目在CD\texttt{CD}CD上的原始顺序输出所选曲目的时长并最后输出总时长。输入格式输入包含多组数据每组数据一行。每行第一个整数为NNN磁带总长度第二个整数为曲目数量ttt随后ttt个整数依次为各曲目的时长。输入直到文件结束。输出格式对于每组数据输出一行首先按原顺序输出被选中的曲目时长每个时长后跟一个空格然后输出sum:和总时长。所有数字之间用空格分隔。样例输入5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2输出1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45题目分析本题本质上是经典的0/1\texttt{0/1}0/1背包问题但物品数量很小t≤20t \le 20t≤20因此可以直接枚举所有子集选择总时长不超过NNN且总时长最大的组合。若多个组合总时长相同输出任意一个均可。由于2201,048,5762^{20} 1,048,5762201,048,576完全可以在时限内完成。代码中使用了带有剪枝的回溯搜索进一步提高了效率。要求输出所选曲目时必须保持它们在输入中的原始顺序因此我们只需按顺序扫描并标记是否选择即可。解题思路暴力枚举回溯法使用深度优先搜索DFS\texttt{DFS}DFS遍历所有可能的子集。每个曲目有两种状态选择或不选择。搜索过程中维护当前已选总时长sum。当sum超过N时剪枝。当搜索完所有曲目后若sum大于已记录的最优值max_sum则更新最优值和对应的选择方案。剪枝优化为了提高效率代码中预先计算了后缀和数组tails[i]表示从第i首曲目到最后一首曲目的时长之和。在递归搜索时若当前sum加上从当前曲目到末尾的所有曲目总时长仍然小于或等于已知最优值max_sum则即使全部选择也无法超越当前最优解因此可以直接剪枝代码中if (sum tails[i] max_sum) return;。此外为了避免重复组合搜索时按顺序依次决定每首曲目是否选择而不是在递归内部再循环枚举起始位置代码中depth参数虽未使用但for循环从depth开始实际上起到了控制顺序的作用。记录方案使用全局数组used和best分别标记当前搜索路径和最优路径的选择情况1表示选择。当sum max_sum时将used复制到best中。最后根据best输出对应曲目时长。特殊情况如果所有曲目总时长不超过N则直接全部选择即可无需搜索代码中首先判断了这一点。复杂度分析最坏情况下需要枚举2t2^t2t种子集t≤20t \le 20t≤20约10610^6106种每次复制方案数组代价为O(t)O(t)O(t)总时间复杂度O(t⋅2t)O(t \cdot 2^t)O(t⋅2t)完全可以接受。空间复杂度O(t)O(t)O(t)。代码实现// CD// UVa ID: 624// Verdict: Accepted// Submission Date: 2016-08-22// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intN,tracks,minutes[25],tails[25];intmax_sum,used[25],best[25];voidbacktrack(intdepth,intsum){if(summax_sum){max_sumsum;copy(used,used25,best);}if(depthtracks){for(intidepth;itracks;i){if(sumtails[i]max_sum)return;if(used[i]0summinutes[i]N){used[i]1;backtrack(depth1,summinutes[i]);used[i]0;}}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinN){cintracks;intsum0;for(inti0;itracks;i){cinminutes[i];summinutes[i];}if(sumN){for(inti0;itracks;i)coutminutes[i] ;coutsum:sum\n;}else{memset(tails,0,sizeof(tails));tails[tracks-1]minutes[tracks-1];for(intitracks-2;i0;i--)tails[i]tails[i1]minutes[i];max_sum0;memset(used,0,sizeof(used));backtrack(0,0);for(inti0;itracks;i)if(best[i])coutminutes[i] ;coutsum:max_sum\n;}}return0;}总结本题是一个小规模的0/1\texttt{0/1}0/1背包问题由于物品数量很少不超过202020直接枚举所有子集即可。代码中采用了回溯加后缀和剪枝进一步提高了效率。输出时保持曲目的原始顺序只需按输入顺序输出被选中的曲目时长即可。该解法简洁高效适合作为回溯法入门练习。

相关新闻