经典动态规划 pascal
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/08/17 23:37:44
经典动态规划 pascal
From Admin
描述 Description
有n种硬币,面值为别为a[1],a[2],a[3]……a[n],每种都有无限多.给定非负整数s,可以选取多少个硬币使得面值和恰好为s?输出硬币数目最小值和最大值
输入格式 Input Format
第1行n
第2行s
第3到n+2行为n种不同的面值
输出格式 Output Format
第1行为最小值
第2行为最大值
样例输入 Sample Input
3
6
1
2
3
样例输出 Sample Output
2
6
时间限制 Time Limitation
1S
注释 Hint
1
From Admin
描述 Description
有n种硬币,面值为别为a[1],a[2],a[3]……a[n],每种都有无限多.给定非负整数s,可以选取多少个硬币使得面值和恰好为s?输出硬币数目最小值和最大值
输入格式 Input Format
第1行n
第2行s
第3到n+2行为n种不同的面值
输出格式 Output Format
第1行为最小值
第2行为最大值
样例输入 Sample Input
3
6
1
2
3
样例输出 Sample Output
2
6
时间限制 Time Limitation
1S
注释 Hint
1
![经典动态规划 pascal](/uploads/image/z/19520504-8-4.jpg?t=%E7%BB%8F%E5%85%B8%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92+pascal)
我来讲一下我的思路:
分两次做:
1、
f1[i]表示取到面值之和为i的最少需要几个银币
当然 f1[a[1]]=1 f1[a[2]]=1 …… f1[a[n]]=1
for i:=1 to s do
for j:=1 to n do
if i-a[j]>0 then
if f1[i]0 then f1[i]:=min(f1[i],f1[i-a[i]]+1)
else f1[i]:=f1[i-a[i]]+1;
2、同理最多也是一样
分两次做:
1、
f1[i]表示取到面值之和为i的最少需要几个银币
当然 f1[a[1]]=1 f1[a[2]]=1 …… f1[a[n]]=1
for i:=1 to s do
for j:=1 to n do
if i-a[j]>0 then
if f1[i]0 then f1[i]:=min(f1[i],f1[i-a[i]]+1)
else f1[i]:=f1[i-a[i]]+1;
2、同理最多也是一样
PASCAL动态规划一水题稀里糊涂就过了,
2.最后的战场(动态规划)pascal (war.pas/c/cpp)
动态规划算法
求动态规划0/1背包问题的经典习题及测试数据
PASCAL 请问我在进行对int64数据快排后作动态规划单调队列操作时,每次的快排关键字怎么取
C语言经典的动态规划题目源程序和解释(c语言)动态规划定义等……越仔细分越高我只是初二的,像NOIP竞赛题,“采药”、“
c语言 数字三角形的动态规划
求一道动态规划题的解答思路以及状态方程
分治算法和动态规划有什么不同和联系?
数学建模中规划的分类时常有什么线性规划和非线性规划 动态规划 非动态规划 多目标规划 单目标规划 到底该怎么具体的给数学
西北工业大学运筹学真题 :1.试述建立动态规划数学模型的步骤及应注意的问题,并说明动态规划的求解方法有
动态