文档介绍：动态规划
一、背包问题：
01背包问题
题目
有N件物品和一个容积为V的背包。第1件物品的体枳是C[1],价值是w[i]o求解将哪些物品装入背包可 使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以
{
scanff%d”,&w[i]);
sum+=w[i];
}
foi(i=l;i<=n;i-H-)
foi(j=sunr'2 ;j>=w[i] j --)
if (flj]<flj-w[i]]+w[i]) flj]=flj-w[i]]+w[i];
printf("%d ",sum-f[suin/2 ] *2);
leturn 0;
}
开心的金明(RQNOJ2)
题目描述：
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他 高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就 行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把 每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件 物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下，使每件物品的价格与重 要度的乘积的总和最大。设第J件物品的价格为叩]，重要度为w[j],共选中了 k件物品，编号依次为jl...jk, 则所求的总和为：\tjl]*wUl]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单.
输入格式：
输入的第1行，为两个正整数，用一个空格隔开：
Nm
(其中N (<30000)表示总钱数，m(<25)为希望购买物品的个数。)
从第2行到第m+1行，第j行给出了编号为J-1
的物品的基本数据，每行有2个非负整数
\'P
(其中v表示该物品的价格(vWlOOOO), p表示该物品的重要度(1~5)) 输出格式：
输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘枳的总和的
最大值(V100000000)
样例输入：
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出：
3900
分析：
本题是经典的01背包问题
在这里钱数表示容量，共m个物品，价格可以看做费用，价格*重要度可•以看做价值。
这下思路就清楚了。
参考程序：
#iiiclude<cstdio>
const int maxii=300014iiaxin=26;
int m,n;
int v[maxm] [niaxm];
int flniaxii];
int niaiii()
(
scanf("%d%d".&n,&m);
for (hit
scanf ("%d%d”,&v[i]‘&p[i])；
for (hit
for (uitj=iij>=v[i]J-)
if (flj-v[i]]+v[i]*p[i]>flj]) f[j]=flj-v[i]]+v[i]*p[i];
pnntR”％d”,f!n]);
retuin 0;
}
金明的预算方案(RQNOJ6)
题目描述：
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让 他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱 就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主 件的，下表就是一些主件与附件的例子： 主件附件
电脑打印机，扫描仪
书柜图书
书桌台灯，文具
工作椅无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。 附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品 规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格 (都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下，使每件物品的价格与重要度 的乘积的总和最大。
设第J件物品的价格为v[j],重要度为w[j],共选中了 k件物品，编号依次为Jl, J2,……，jk,则所 求的总和为：v[jl]*w[jl]+vU2]*wU2]+ •••+v[jk]*w[jk]o (其中*为乘号)请你帮助金明设计一个满足要求的 购物单。
输入格式：
输入文件的第1行，为两个正整数，用一个空格隔开：
Nm
其中N (<32000)表示总钱数，m «60)为希望购买物品的个数。)
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数