acm中dp问题简单入门讲解.docVIP

ACM暑期集训报告 院 系： 专 业： 年 级： 学 号： 姓 名： 日 期： 西南交通大学 目 录 目 录 1 第1章 动态规划（dp） 2 1.1 简介 2 1.2 教师内容 5 1.3 基本dp——背包问题 6 1.4若干经典dp及常见优化 9 1.5类似题目 10 参考文献 31 附录1 暑期集训心得体会 31 动态规划（dp） （标题采用2号黑体居中，下空1行） 1.1 简介 （标题采用四号黑体，正文内容采用小四号字体，1.5倍行距） 在解决问题的时候我们经常遇到这种问题：在多种方式的操作下我们如何得到一个最优的方式让我们得到满意的结果。这时候我们大多人的思想就是贪心。不错贪心确实是一个不错的算法，首先他简单容易想到，我们在操作起来也比较容易。现在我推荐几道我们oj上的贪心算法的题：soj1562药品运输 soj1585 Climbing mountain。为了引入动归算法我先拿 药品运输这道题简单说一下贪心算法。 示例1：药品运输（题目采用小四号Times New Roman字体） Description 5.12大地震后，某灾区急需一批药品，现在有N种药品需要运往灾区，而我们的运输能力有限，现在仅有M辆运输车用来运输这批药品，已知不同的药品对灾区具有不同的作用（“作用”用一个整数表示其大小），不同的药品需要的运输力（必要的车辆运载力）不同，而不同的车辆也具有不同的运输力。同时，我们希望不同的药品用不同的车辆来运输（避免发生混淆）。 现在请你帮忙设计一方案，来使得运往灾区的药品对灾区的作用最大。 Input 第一行包含一个整数T，表示需要处理的测试数据组数。每一组第一行包括两个整数N,M，分别表示药品总数，及车辆总数。接着第二行包含N个整数（pi=10000），分别表示每种药品的作用。接着第三行包含N个整数，分别表示每种药品必须得运载力(wi=1000)。接着第四行包含M个整数，表示每辆车的运输力(c=1000)；（T=10; N,M=1000） Output 输出包括T行，每行仅一个整数，表示最大的作用值。 Sample Input 1 1 1 10 3 7 Sample Output 10 So easy，right？不过是不是我们所有的问题这样都能很随意的解决呢？Now，接下来的题目，你会发现我们的贪心，贪不过去了。。。。。。 示例2：硬币问题（soj 1787） Description 有 N 种不同面值的硬币，每种硬币都是有限个，给定一个上限钱数 W, 问用这些硬币可组成不超过 W 的最大价值． Input 输入有多组测试数据。 每一组测试数据为如下形式： W N n1 D1 n2 D2 ... nN DN W 和 N 分别表示上限钱数 和 有 N 种不同面值的硬币，n（i）和D（i）表示面值为 D（i）的硬币数量为 n（i），其中有 1 = i = N. 0 = W = 100000, 0 =N = 10, 0 = n(i) = 1000, 1 = D(i) = 1000. Output 对于每一组测试数据，输出这些硬币可组成不超过 W 的最大价值． Sample Input 735 3 4 125 6 5 3 350 633 4 500 30 6 100 1 5 0 1 735 0 0 3 10 100 10 50 10 10 Sample Output 735 630 0 0 现在我们试一试如果每一次都取满足条件的最大面值的硬币那么得到的答案是不是正确的呢？拿第一组数据为例：735 3 4 125 6 5 3 350 取350 剩下 385 取350 剩下 35 取 5 剩下 30 依次再取5 五次。 最终我们取到了350*2+5*6=730 咦。。。。不对啊？ 如果 350+125*3+5*2=735岂不是更多？可是我们每一次都取最优解啊，为啥结果不是最优的呢？问题出在第一种取法没有考虑到空间的最大利用化。下面我们引入了动态规划，又习惯称之为dp。 严格的说，动态规划程序设计是对解最优化问题的一种途径