动态规划
一、背包问题： 01背包问题 题目
有N件物品和一个容积为V的背包。第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
二维方程：f[i,v]:=max(f[i-1,v],f[i-1,v-c[i]]+w[i]) 一维方程：f[v]:=max(f[v],f[v-c[i]]+w[i]);
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品放或不放，那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
1． 采药(RQNOJ15)； 题目描述：
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？ 输入格式：
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 输出格式：
输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 样例输入： 70 3 71 100 69 1 1 2
样例输出： 3
分析：
这是一道典型的0/1背包问题，把采其中一种的时间看做标准模型中的每个物品的体积，把规定的时间看做背包的总容量，这样问题和基本模型就一样了。 参考程序： #include
using namespace std; int ti[101],money[101]; int f[1001]; int main() {
int t,m,i,j;
scanf(\ for(i=1;i<=m;i++)
scanf(\ for(i=1;i<=m;i++) for(j=t;j>=ti[i];j--)
if(f[j] 2． 拔河比赛(RQNOJ72) 题目描述： superwyh的学校要举行拔河比赛，为了在赛前锻炼大家，老师决定把班里所有人分为两组，进行拔河比赛,为了避免其中一方的实力过强老师决定以体重来划分队伍，尽量保持两个队伍的体重差最少，因为老师对结果没兴趣，所以只告诉老师最小的体重差是多少就行了。这个受苦受累的任务就交给superwyh了，因为这两天superwyh的后背间谍sjh闹肚子了，所以只好superwyh亲自去调查每个人的体重，但是仅仅知道体重依然难以确定到底如何分配队伍，请各位oier帮助superwyh出出主意。 输入格式： 第一行为人数(1<=n<=100)，从第二行开始是每个人的体重(0<=m<=100)。 输出格式： 最小体重差。 样例输入： 4 10 23 41 12 样例输出： 4 分析： 实际是个隐藏很深的01背包问题，先把所有人的重量加起来除以二当作背包容积v，把他們的體重同時看成是價值和重量， 要使重量差最小 也就是在里面选一些人分成两组，使这两组人的重量和最接近v。 比如樣例數據，可以求出總重量是86，除以2就是43，再背包一下，求出是41，輸出86-41*2即可 参考程序： #include int main() { scanf(\ sum=0; for(i=1;i<=n;i++) { scanf(\ sum+=w[i]; } for(i=1;i<=n;i++) for(j=sum/2;j>=w[i];j--) if (f[j] 3． 开心的金明(RQNOJ2) 题目描述： 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单. 输入格式： 输入的第1 行，为两个正整数，用一个空格隔开： N m （其中N（<30000）表示总钱数，m(<25)为希望购买物品的个数。） 从第2 行到第m+1 行，第j 行给出了编号为j-1 的物品的基本数据，每行有2 个非负整数 v p （其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5）） 输出格式： 输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的 最大值（<100000000） 样例输入： 1000 5 800 2 400 5 300 5 400 3 200 2 样例输出： 3900 分析： 本题是经典的01背包问题 在这里钱数表示容量，共m个物品，价格可以看做费用，价格*重要度可以看做价值。 这下思路就清楚了。 参考程序： #include const int maxn=30001,maxm=26; int m,n; int v[maxm],p[maxm]; int f[maxn]; int main() { scanf(\ for (int i=1;i<=m;i++) scanf (\ for (int i=1;i<=m;i++) for (int j=n;j>=v[i];j--) if (f[j-v[i]]+v[i]*p[i]>f[j]) f[j]=f[j-v[i]]+v[i]*p[i]; printf(\ return 0; } 4． 金明的预算方案(RQNOJ6) 题目描述： 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，??，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。 输入格式： 输入文件的第1行，为两个正整数，用一个空格隔开： N m 其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q （其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）
相关推荐：
loading