算法设计 1 )问题:有 n 个物品,第 i 个物品价值为 vi ,重量为 wi ,其中 vi 和 wi 均为非负数,背包的容量为 W , W 为非负数。现需要考虑如何选择装入背包的物品,使装入背包的物品总价值最大。 1) 一个序列有 N 个数: A[1],A[2], ... ,A[N] ,求出最长上升子序列的长度( LIS : longest increasing subsequence) 。例如,对于序列 (1, 7, 3, 5, 9, 4, 8) ,有它的一些上升子序列,如 (1, 7), (3, 5, 9) , (3, 4, 8) 等等。这些子序列中最长的长度是 4 ,比如子序列 (1, 3, 5, 9) , (1, 3, 5, 8) 和 (1, 3, 4, 8). 3 )问题描述 设有一个长度 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种分法,使得这 K+1 个部分的乘积能够为最大。 例子:有一个数字串 : 312 ,当 N=3 , K=1 有以下两种分法: 1 ) 3*12=36 2 ) 31*2=62 这时,符合题目要求的结果是: 31*2=62 现在,请你设计一个程序,求得正确的答案。