从给定的N个正数中选取若干个数之和最接近M【01背包实现】

您所在的位置:网站首页 如何从一堆数字中随机一个数字 从给定的N个正数中选取若干个数之和最接近M【01背包实现】

从给定的N个正数中选取若干个数之和最接近M【01背包实现】

2024-07-14 15:10| 来源: 网络整理| 查看: 265

题目描述:

给定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