1 / 23
文档名称:

noip普及讲座4动态规划2.ppt

格式:ppt   大小:137KB   页数:23页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

文档介绍:经典例题讲解
【例题1】装箱问题〔noi openjudge 8785〕
问题描绘:
有一个箱子容量为V〔正整数,0<=v<=20000〕,同时有n个物品〔0< n<=30〕,每个物品有一个体积〔正整数〕。

要求n个物品中,任取假设干个装入箱内,使箱子的剩余空间为最小。

输入
第一行是一个整数V,表示箱子容量。
第二行是一个整数n,表示物品数。
接下来n行,每行一个正整数〔不超过10000〕,分别表示这n个物品的各自体积。
输出
一个整数,表示箱子剩余空间。


经典例题讲解
样例输入
24
6
8
3
12
7
9
7
样例输出
0。


经典例题讲解

【问题分析】
状态:
f[i,j]代表前i个物体装在j重的包里的最优解
方程:
f[i,j]=max(f[i-1,j],f[i-1,j-a[i]);


【程序实现】


经典例题讲解
【例题2】宝石手镯〔usaco〕
问题描绘:
贝茜在珠宝店闲逛时,买到了一个中意的手镯。很自然地,她想从她搜集的N(1 <= N <= 3,402)块宝石中选出最好的那些镶在手镯上。对于第i块宝石,它的重量为W_i(1 <= W_i <= 400),并且贝茜知道它在镶上手镯后能为自己增加的魅力值D_i(1 <= D_i <= 100)。由于贝茜只能忍受重量不超过M(1 <= M <= 12,880)的手镯,她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你,告诉了你她所有宝石的属性以及她能忍受的重量,希望你能帮她计算一下,按照最合理的方案镶嵌宝石的话,她的魅力值最多能增加多少。


经典例题讲解
【输入格式】
输入的第一行有两个整数N(1 <= N <= 3,402)和M(1 <= M <= 12,880),接下来的N行每行两个整数,分别表示宝石重量和魅力值。
【输出格式】
输出只包括一行,这一行只包含一个整数,表示魅力值最多能增加多少。
【样例输入】
3 70
71 100
69 1
1 2
【样例输出】
3


经典例题讲解

【问题分析】
状态:
f[i,j]代表前i个宝石戴在j重的手上获得的最大魅力值
方程:
f[i,j]=max(f[i-1,j],f[i-1,j-a[i])+b[i];



经典例题讲解
【例题3】奶牛打工
问题描绘:
奶牛Bassie去DQ打工,遇到一个客人给了一张好大面值的钞票,于是Bassie不得不为了给这位顾客找零而面对这样一个问题:如今店里一共有n种硬币,对这些不同种的硬币进展编号,编号为i的硬币面值为a[i] 。因为奶牛的手指头是有限的,因此他只能向你求助啦。(总需找零数为total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)求一共有多少种解决方案?

分享好友

预览全文

noip普及讲座4动态规划2.ppt

上传人:1557281760 2021/12/5 文件大小:137 KB

下载得到文件列表

noip普及讲座4动态规划2.ppt

相关文档