算法,集合取数计算正整数集合N,最多有数字1000个,给定一个正整数K从N中取任意个数字相加,和为SUM,SUM不大于K求SUM可以达到的最大值求问算法思想···

Question

算法,集合取数计算
正整数集合N,最多有数字1000个,给定一个正整数K
从N中取任意个数字相加,和为SUM,SUM不大于K
求SUM可以达到的最大值
求问算法思想···

Answer 1

这是一个比较典型的01背包问题,可以用动态规划的方法来解决.
首先,对问题进行一点小小的变形,即将K看做背包容量v,而每一个集合中的数字,看作一件物品,它的重量c和价值w均为其数值本身.
然后,用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
至此,即可编写程序依照上面的状态转移方程对f[N][K]进行求解了.
如果要对求解的过程进行优化,可以参考01背包问题的具体讲解,网上有很多,这里就不多介绍了.