背包问题思路.doc

背包问题思路问题描述在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W2Wn，与之相对应的价值为P1,P2Pn。求出获得最大价值的方案。注意：在本题中，所有的重量值均为整数。可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。考虑用动态规划的方法来解决，这里的：阶段是：在前N件物品中，选取若干件物品放入背包中；状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；决策是：第N件物品放或者不放；由此可以写出动态转移方程：我们用fi,j表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值fi,j=maxfi-1,j-Wi+Pi (j=Wi), fi-1,j这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是fm,w算法设计如下：for(i=1;i=m;i+) /*m是物品的个数*/ for(j=0;j=vi) x=fi-1j-vi+pi; if(xfij) fij=x; 采药(medic.pas/c/cpp)【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M =ai1 j=物品重量时，fij=maxfi-1j,fi-1j-ai1+ai2Ai1是物品的重量，ai2是物品的价值3、当jai1 fij=fi-1j【数据规模】对于30%的数据，M = 10；对于全部的数据，M = 100。动态规划：记f(t, m)是如果只采前m株草药，在时间t里能够得到的最大价值。可以得到f(t, m) = maxf(t, m 1), f(t 采第m株草药需要的时间, m 1) + 第m株草药的价值时间复杂度O(T * M)。答案：#includeint main()FILE *fp;float f1011001=0,p101=0;int t,m,w101=0,i,j;fp=fopen(tw1.in,r);fscanf(fp,%d%d,&t,&m);for(i=1;i=m;i+)fscanf(fp,%d%f,&wi,&pi);fclose(fp);fp=fopen(tw1.out,w);for(i=1;i=m;i+)for(j=1;j=wi&(pi+fi-1j-wi)fij)fij=pi+fi-1j-wi;fprintf(fp,%.0f,fmt);fclose(fp);return 0;2.开心的金明(happy.pas/c/cpp)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N（30000）表示总钱数，m（25）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900答案：#includefloat f2630001=0;int main()FILE *fp;float p26=0;int t,m,w26=0,i,j;fp=fopen(tw2.in,r);fscanf(fp,%d%d,&t,&m);for(i=1;i=m;i+)fscanf(fp,%d%f,&wi,&pi);fclose(fp);fp=fopen(tw2.out,w);for(i=1;i=m;i+)for(j=1;j=wi&(pi*wi+fi-1j-wi)fij)fij=pi*wi+fi-1j-wi;fprintf(fp,%.0f,fmt);fclose(fp);return 0;合唱队形 解题报告 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK，则他们的身高满足T1.Ti+1TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。- 输入文件输入文件chorus.in的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。- 输出文件输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。- 样例输入8186 186 150 200 160 130 197 220A1 a1- 样例输出4- 数据规模对于50的数据，保证有n=20；对于全部的数据，保证有n=100。动态规划。最基本的想法是：枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为O(n3)，算法实现起来也很简单。接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设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=sum=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，那么，紧接在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个数满足：1st26, 2wt-s ） 第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。