从给定的N个正数中选取若干个数之和最接近M【01背包实现】 |
您所在的位置:网站首页 › 如何从一堆数字中随机一个数字 › 从给定的N个正数中选取若干个数之和最接近M【01背包实现】 |
题目描述:
给定N个数字,从N个数字中选择任意k个数字,使之和sum最接近M。 注意:最接近M的意思很多,具体要根据题目分析: 比如sum是否可以与M相等? 再比如sum必须小于M,还是说sum可以大于M? 例如有3个数字:14 15 20 M=33 如果sum必须小于M,那么最接近的就是29(14+15),如果可以大于,那么答案就是35 解题思路: 我们可以把M看做是一个背包,而给定的数字是价值和重量相等的物品,在容量一定的情况下,我们要选择出价值最大的组合,也就是最接近容量M的组合。 一种情况:限制条件 sum>n>>m; for (int i=1; i>a[i]; for (int i=1; i=a[i]; j--){ f[j]=max(f[j],f[j-a[i]]+a[i]); } } //for (int i=1; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |