背包问题ppt课件

.,背包问题,有一个贼在偷窃一家商店时发现有n件物品:第i件物品值vi元，重wi磅，(1in)，此处vi和wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下m磅的东西(m为整数)。有两种偷窃方式:1.01背包问题如果每件物品或被带走或被留下，小偷应该带走哪几件东西?2.部分背包问题如果允许小偷可带走某个物品的一部分，小偷应该带走哪几件东西，每件东西的重量是多少?,.,采用贪心策略来解决部分背包问题:对每件物品计算其每磅价值viwi按每磅价值单调递减的顺序对物品排序。例如，总共有三件物品和一个背包,开始时对具有每磅价值最大的物品尽量多拿一些。如果拿完了该物品,算法：begin读入数据；计算物品的单位重量价值Ti=vi/wi，并将它们从大到小排序；依次选择单位价值较大的物品装入背包，直至不能装入；输出最大价值总和s和装货方案；end;,后仍可以取一些其他物品时，再取具有每磅价值次大的物品，一直继续下去，直到不能取为止.,.,部分背包问题中，在考虑是否把一件物品加到背包中时，不需要把加入该物品的子问题解与不取该物品的子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。,若对01背包问题采取贪心策略，顺序取物品1和2,在01背包问题中不应取物品1的原因在于这样无法将背包填满，空余的空间降低了它的每磅价值，因此当我们考虑是否要把一件物品加到背包中时，必须对把加进该物品的子问题的解与不取该物品的子问题的解进行比较。由这种方式形成的子问题导致了许多重迭的子问题。对于这一类虽具有最优化结构性质、但产生的子问题互为重迭的试题，一般采用动态程序设计的方法求解。,最优解取的是物品2和，没有取物品1。两种包含物品1的可能解都不是最优解,.,01年初4装箱问题：一箱的容量为V(0V20000)，同时有n个物品(0n30)，每个物品有一个体积(正整数)。要求从n个物品中，任取若干个装入箱内，使剩余空间为最小。样例：输入：24表箱子容量6n个物品8312797输出：0表箱剩余空间,讨论：阶段？状态？决策？状态转移？,可取的物品有i个,能组成的各种体积,加入i能组成满足条件的体积(取、不取),fi=maxfj+wi|取iji=n,fi=maxfj|不取iji=n,.,01年初4装箱问题：一箱的容量为V(0V20000)，同时有n个物品(0n30)，每个物品有一个体积(正整数)。要求从n个物品中，任取若干个装入箱内，使剩余空间为最小。样例：输入：24表箱子容量6n个物品8312797输出：0表箱剩余空间,i0123456,tt,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,讨论：阶段？状态？决策？状态转移？,可取的物品有i个,能组成的各种体积,加入i能组成满足条件的体积(取、不取),fi=maxfj+wi|取iji=n,fi=maxfj|不取iji=n,t,.,programc2001_4;vari,k,n,v:integer;w:array1.30ofinteger;b:array0.20000of0.1;beginreadln(v);readln(n);fori:=1tondoread(wi);fillchar(b,sizeof(b),0);bv:=1;fori:=1tondofork:=0tov-widoifbk+wi=1thenbk:=1;i:=0;whilebi=0doi:=i+1;writeln(i);end.,.,采药NOIP2005,【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】7037110069112,(medic.pas/c/cpp),【样例输出】3【数据规模】对于30%的数据，Ma)thena:=b;enddpi,j:=a;end;end;writeln(dpt,m);end.,用动规求解：,.,第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行，为两个正整数，用一个空格隔开：Nm(其中N(30000)表示总钱数，m(25)为希望购买物品的个数。)从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（gi-1,j)决策Thengi,j:=gi-1,j-pi+wi选取i物品Elsegi,j:=gi-1,j;不选取i物品Writeln(gm,n),1000580024005300540032002【输出样例】3900,p,w,i,j,g,gi,j：已考察到第i个物品,费用为j的所选物的价格与重要度的乘积的最大总和,.,varp:array0.30000oflongint;i,j,w,v,m,n:integer;beginreadln(n,m);读入钱数n,物品数mfori:=1tomdo以物品为阶段beginreadln(v,w);读入费用v重要度wforj:=ndowntovdo以总费用n为状态if(v*w+pj-vpj)决策:当前用j费用,考察到第i个物品的最大乘积thenpj:=v*w+pj-v;end;writeln(pn);end.,.,vara:array-1.10,-1.2000oflongint;w,p,c:array1.10oflongint;m,n,i,j,k:integer;beginread(n,m);m:=5;fillchar(a,sizeof(a),0);fori:=1tomdobeginr