背包问题思路.doc

1、背包问题思路问题描述在 M 件物品取出若干件放在空间为 W 的背包里，每件物品的重量为 W1，W2Wn，与之相对应的价值为 P1,P2Pn。求出获得最大价值的方案。注意：在本题中，所有的重量值均为整数。可以看出如果通过第 N 次选择得到的是一个最优解的话，那么第 N-1 次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。考虑用动态规划的方法来解决，这里的：阶段是：在前 N 件物品中，选取若干件物品放入背包中；状态是：在前 N 件物品中，选取若干件物品放入所剩空间为 W 的背包中的所能获得的最大价值；决策是：第 N 件物品放或者不放；由此可以写出动态转移方程：我们用 fi,j表示

2、在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值fi,j=maxfi-1,j-Wi+Pi (j=Wi), fi-1,j这样，我们可以自底向上地得出在前 M 件物品中取出若干件放进背包能获得的最大价值，也就是fm,w算法设计如下：for(i=1;i=vi) x=fi-1j-vi+pi;if(xfij)fij=x;采药(medic.pas/c/cpp)【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药

3、，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。 ” 如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件 medic.in 的第一行有两个整数 T（1 =ai1 j=物品重量时， fij=maxfi-1j,fi-1j-ai1+ai2Ai1是物品的重量，ai2是物品的价值3、当 jint main()FILE *fp;float f1011001=0,p101=0;int t,m,w101=0,i,j;fp=fopen(“tw1.in“,“r“);fscanf(fp,“%d%d“

4、,for(i=1;i=wifprintf(fp,“%.0f“,fmt);fclose(fp);return 0;2.开心的金明(happy.pas/c/cpp)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行” 。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 15 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元） 。他希望在不超过

5、N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第 j 件物品的价格为 vj，重要度为 wj，共选中了 k 件物品，编号依次为j1， j2， ，j k，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。 （其中* 为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件 happy.in 的第 1 行，为两个正整数，用一个空格隔开：N m（其中 N（float f2630001=0;int main()FILE *fp;float p26=0;int t,m,w26=0,i,j;fp=fopen(“tw2.in“,“r“);fscan

6、f(fp,“%d%d“,for(i=1;i=wifprintf(fp,“%.0f“,fmt);fclose(fp);return 0;合唱队形 解题报告N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K 位同学从左到右依次编号为1，2，K ，他们的身高分别为T1， T2， ，TK ， 则他们的身高满足T1Ti+1TK(1动态规划。最基本的想法是：枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为O(n3)，算法实

7、现起来也很简单。接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设bi表示了1 - i的最长上升序列，ci表示了i - n的最长下降序列，那么，di = bi +ci - 1（两个数组中i被重复计算了）那么，我们只需要先求好最长上升和下降序列，然后枚举中间最高的同学就可以了。(在写状态转移方程时要满足无后效性)求最长递增序列的经典状态转移方程为：最初时:bi=1;状态转移方程为bi = maxbi,bj+1, 其中 ji=n, 且 listjlisti写出最长递减序列的经典状态转移方程为：ci = maxci,cj+1, 其中 1=ij=n, 且 listjlistik=s

8、um=max(bI+cI)-1 3.Jam 的计数法（count.pas/c/cpp） *题目部分 【问题描述】 Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母） ，英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为 Jam 数字。在 Jam 数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam 还指定使用字母的范围，例如，从 2 到 10，表示只能使用b,c,d,e,f,g,h,i,j这些字母。如果再规定位数为 5

9、，那么，紧接在 Jam 数字“bdfij”之后的数字应该是“bdghi ”。 （如果我们用 U、V 依次表示 Jam 数字“bdfij”与“bdghi”，则 UV，且不存在 Jam 数字 P，使 UPV） 。你的任务是：对于从文件读入的一个 Jam 数字，按顺序输出紧接在后面的 5 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。 【输入文件】 输入文件 counting.in 有 2 行，第 1 行为 3 个正整数，用一个空格隔开： s t w （其中 s 为所使用的最小的字母的序号，t 为所使用的最大的字母的序号。w 为数字的位数，这 3 个数满足：1 st 26, 2w t-s ） 第 2 行为具有 w 个小写字母的字符串，为一个符合要求的 Jam 数字。 所给的数据都是正确的，不必验证。 【输出文件】 输出文件 counting.out 最多为 5 行，为紧接在输入的 Jam 数字后面的 5 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。每行只输出一个 Jam 数字，是由w 个小写字母组成的字符串，不要有多余的空格。 【输入样例】 2 10 5 bdfij 【输出样例】 bdghi bdghj bdgij bdhij befgh