背包问题ppt课件

：对　T=7n=6.vartt,vv:array[0..200]ofinteger;{存采i药时间，药价值}dp:array[0..1005,0..105]ofinteger;{dp[i,j]:i:采药秘用时间,j:已考察药的数量}a,b,i,jt,m:integer;beginreadln(t,m);{读入采药时间，药数量}fori:=1fomdoreadln(tt[i],vv[i]);{读入采i药时间，药价值}fori:=1totdo{阶段-采药时间为i}beginforj:=1tomdo{状态--考察第j种药}begina:=dp[i,j-1];{考察第j-1种药,用时为i}if(i>=tt[j])then{若第j种药的采取时间小于i,则考察j药}begin{决策}b:=dp[i-tt[j],j-1]+vv[j];{在已用(i-tt[j])时间,采(j-1)药时，又取第j种药}if(b>a)thena:=b;enddp[i,j]:=a;end;end;writeln(dp[t,m]);end.用动规求解：.第 2 题   快乐的金明  ( happy.pas/c/cpp )【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。.【输入文件】输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：N  m(其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。)从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v  p（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。【输出样例】3900购第2、3、5件物品【输入样例】1000 51000元钱，有5件物品供选择800 2第1件物品，价800，重要度为2400 5第2件物品，价400，重要度为5300 5400 3200 2第5件物品，价200，重要度为2第 2 题   快乐的金明  ( happy.pas/c/cpp ).【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900【算法分析】本题考察的是基本的01背包问题，当然搜索也可以做全对，数据量太大了。ij1、以物品为阶段i2、以所用费用为状态j3、以取乘积最大为决策4、状态转移a[i,j]：考察了i种物品，用去j钱的最大乘积w[i]:第i种物品重p[i]：第i种物的价值a[i,j]:=max{a[i-1,j],a[i-1,j-w[i]]+w[i]*p[i]}a第 2 题   快乐的金明  ( happy.pas/c/cpp ).【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900ijfori:=1tokdo{以物品为阶段i}begin{以所用费用j为状态}forj:=1tow[i]-1doa[i,j]:=a[i-1,j]{用j钱买不到i物品}forj:=w[i]tondo{用j钱可买到i物品}ifa[i-1,j]= p [ i ] ) and( g [ i - 1 , j - p [ i ] ] + w [ i ] > g [ i - 1 , j ] ){决策}Then g [ i , j ] := g [ i - 1 , j - p [ i ] ] + w [ i ]{选取i物品}                Else g [ i , j ] := g [ i - 1 , j ] ;{不选取i物品}    Writeln ( g [ m , n ] )1000 5800 2400 5300 5400 3200 2【输出样例】3900pwijgg [ i , j ]：已考察到第i个物品,费用为j的所选物的价格与重要度的乘积的最大总和.varp:array[0..30000]oflongint;i,j,w,v,m,n:integer;beginreadln(n,m);{读入钱数n,物品数m}fori:=1tomdo{以物品为阶段}beginreadln(v,w);{读入费用v重要度w}forj:=ndowntovdo{以总费用n为状态}if(v*w+p[j-v]>p[j]){决策:当前用j费用,考察到第i个物品的最大乘积}thenp[j]:=v*w+p[j-v];end;writeln(p[n]);end..vara:array[-1..10,-1..2000]oflongint;w,p,c:array[1..10]oflongint;m,n,i,j,k:integer;beginread(n,m);m:=5;fillchar(a,sizeof(a),0);fori:=1tomdobeginread(w[i],p[i]);c[i]:=w[i]*p[i];end;fori:=1tomdobeginforj:=1tow[i]-1doa[i,j]:=a[i-1,j];forj:=w[i]tondoifa[i-1,j]