这里是关于背包型动态规划的题目以及程序
背包型动态规划
装箱问题
题目描述 Description
有一个箱子容量为 $V$(正整数,$ 0 \leq V \leq 20000$),同时有$n$个物品($0 < n \leq 30$),每个物品有一个体积(正整数)。
要求$n$个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述 Input Description
一个整数$v$,表示箱子容量
一个整数$n$,表示有n个物品
接下来$n$个整数,分别表示这$n$ 个物品的各自体积
输出描述 Output Description
一个整数,表示箱子剩余空间。
样例输入 Sample Input
24
6
8
3
12
7
9
7
样例输出 Sample Output
0
数据范围及提示 Data Size & Hint
无
The Code Of My Program
1 | /********************* |
乌龟棋
题目描述 Description
小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N个格子。$1 \; 2 \; 3 …… N-1 \; N$ ,每个格子上一个分数(非负整数)。棋盘第$1$格是唯一 的起点,第$N$格是终点。
游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中$M$张爬行卡片,分成$4$种不同的类型($M$张卡片中不一定包含所有$4$种类型的卡片,见样例),每种类型的卡片上分别标有$1、2、3、4$四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择 一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。
游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?
输入描述 Input Description
输入的每行中两个数之间用一个空格隔开。 第$1$行$2$个正整数$N$和$M$,分别表示棋盘格子数和爬行卡片数。 第$2$行$N$个非负整数,$a_1 \; a_2 \; …… \; a_N$,其中$a_i$表示棋盘第$i$个格子上的分数。 第$3$行$M$个整数,$b_1 \; b_2 \; …… \; b_M $,表示$M$张爬行卡片上的数字。 输入数据保证到达终点时刚好用光$M$张爬行卡片,即$ N - 1 = \sum_{i=1}^{M} b_i$
输出描述 Output Description
输出一行一个整数
样例输入 Sample Input
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1
样例输入 Sample Input
455
数据范围及提示 Data Size & Hint
对于$30%$的数据有$1 \leq N \leq 30,1 \leq M \leq 12$。
对于$50%$的数据有$1 \leq N \leq 120,1 \leq M \leq 50$,且 $4$ 种爬行卡片,每种卡片的张数不会超过$20$。
对于$100%$的数据有$1 \leq N \leq 350,1 \leq M \leq 120$,且 $4$ 种爬行卡片,每种卡片的张数不会超过$40$;
$0 \leq ai \leq 100,1 \leq i \leq N,1 \leq bi \leq 4,1 \leq i \leq M$。输入数据保证$ N - 1 = \sum_{i=1}^{M} b_i$
1 | /********************* |