题目描述
设有一排数,共n个,例如:22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小.
输入、输出数据格式与“石子合并”相同。
输入样例:
4
12 5 16 4
输出样例:
-12 -5 16 4
17 -16 -4
-17 -20
37
背包问题
设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为XK,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于XK,而价值的和为最大。
输入数据:
第一行两个数:物品总数N,背包载重量XK;两个数用空格分隔;
第二行N个数,为N种物品重量;两个数用空格分隔;
第三行N个数,为N种物品价值; 两个数用空格分隔;
输出数据:
第一行总价值;
以下N行,每行两个数,分别为选取物品的编号及数量;
输入样例:
4 10
2 3 4 7
1 3 5 9
输出样例:
12
2 1
4 1