求free pascal 动态规划题
发布网友
发布时间：2022-04-29 20:51
共2个回答
热心网友
时间：2022-06-22 15:02
第一行：二个整数 n 和m，分别为物品数和背包容量（n<=30，m<=200）。
接下来有 n 行，每行有两个实数wi，ci，分别为背包 i 的重量和价值。输出文件：（package.out）只有一个数据，表示最大的总价值。输入样例：package.in10 42 13 34 57 9输出样例：package.out12 完全背包（knapsack.pas）给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 ci，背包的容量为 m。问应如何选择装入背包中的物品，若每一件物品无限个（同一种物品可以多次选取），使得装入背包中物品的总价值最大？输入文件：（knapsack.in）
第一行：二个整数 n 和m，分别为物品数和背包容量（n<=30，m<=200）。
接下来有 n 行，每行有两个实数wi，ci，分别为背包 i 的重量和价值。输出文件：（knapsack.out）只有一个数据，表示最大的总价值。输入样例：knapsack.in11 42 13 34 57 9输出样例：knapsack.out12 货币系统（money.pas）母牛们不但创建了他们自己的*而且建立了自己的货币系统。他们对货币的数值感到好奇。传统地，一个货币系统是由于某种原因，5，10，20或25，50，100的单位面值组成的。母牛们想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。举例来说，使用一个货币系统{1，2，5，10}产生18单位面值的一些可能的方法是：18*1，9*2，8*2+2*1，3*5+2*1等等。写一个程序来计算用给定的货币系统来构造一个确定的面值有多少种方法。输入文件：（money.in）第一行：两个整数v（1<=v<=25）和（1<=n<10000）。第二～v+1行：可用的货币v个整数（每行一个）。输出文件：（money.out）一个数据，表示可能构造的方案数。输入样例：money.in3 10125输出样例：money.out10 竞赛总分（inflate.pas）学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能地多得分。现在要进行一次竞赛，总时间t固定，有若干类型可选择的题目，每种类型题目可选入的数量不限，每种类型题目有一个si（解答此韪所得的分数）和ti（解答此韪所需的时间），现要选择若干题目，使解这些题的总时间在t以内的前提下，所得的总分最大。输入包括竞赛的时间，m（1<=m<=10000）和题目类型数目n（1<=n<=10000）。后面的每一行将包括两个整数来描述一种“题型”：第一个整数说明解决这种题目能得的分数（1<=points<=10000），第二个整数说明说明解决这种题目所需的时间（1<=minutes<=10000）.输入文件：（inflate.in）第一行：两个整数竞赛的时间m和题目类型数目n。第二～n+1行：两个整数，每种类型题目的分数和耗时。输出文件：（inflate.out）一个数据，表示在给定的固定时间里得到的最大分数。输入样例：inflate.in300 4100 60250 120120 10035 20输出样例：inflate.out605质数和分解（prime.pas）任何大于1 的自然数n，都可以写成若干个大于等于2且小于等于n的质数之和表达式（包括只有一个数构成的和表达式的情况），并且可能有不止一种质数和的形式。例如，9的质数和表达式就有四种本质不同的形式：9=2+5+2=2+3+2+2=3+3=3=2+7。这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。试编程求解自然数n可以写成多少种本质不同的质数和表达式。输入文件：prime.in一个自然数n，2<=n<=200。输出文件：prime.outN的本质不同的质数和表达式的数目。输入样例： 输入样例：2 200输出样例：1 9845164 采药（medic.pas）辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？
【输入文件】medic.in
第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 【输出文件】medic.out
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。 开心的金明(happy.pas)金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+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）。【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2【输出样例】
3900 最小乘车费用(busses.pas)假设某条街上每一公里就有一个公共汽车站，并且一种可能的乘车费用如下表：
公里数12345678910 费用122131404958697990101 而任意一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。
注意：10公里的费用比1公里小的情况是允许的。 【输入文件】(busses.in) 输入共两行；
第一行为10个不超过200的整数，依次表示行驶1～10公里的费用，相邻两数间用一个空格隔开；
第二行为某人想要行驶的公里数。【输出文件】(busses.out)输出仅一行，包含一个整数，表示行使这么远所需要的最小费用。【输入样例】 12 21 31 40 49 58 69 79 90 101 15 【输出样例】147
热心网友
时间：2022-06-22 15:02
�0�2�0�2在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大重新排列。他退休之后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，从输入文件读入列车初始的车厢顺序，计算最少用多少步就能将车厢排序，把最少的步数记录在输出文件中。
输入：输入文件的每行是一用空格符分隔、最多为50个元素的正整数数列，该数列记录了一列车初始的车厢顺序，当输入行的第一个数为0，表示文件结束。
输出：输出文件与输入文件有同样的行数。每一行只有一个整数记录了对应输入文件该行列车车厢排序所需的最少步数。
输入样例：
4�0�23�0�22�0�21
0
输出样例：
6
0
