M选n 递归编程 java_搜狗面试题：从N个正实数中选若干个数之和最接近M的递归实现...

傷城~ 2021-09-07 06:13 115阅读 0赞

//搜狗：有N个正实数(注意是实数，大小升序排列) x1 , x2 ... xN，另有一个实数M。

//需要选出若干个x，使这几个x的和与 M 最接近。 请描述实现算法，并指出算法复杂度。

public void FindDouble(double\[\] A,bool\[\] Exsits, int N,double M,int i,double PreCurrSum,bool Exists)

\{

double theCurrSum = PreCurrSum + (Exists ? A\[i - 1\] : 0);

Exsits\[i - 1\] = Exists;

double theNewDelta = Math.Abs(theCurrSum - M);

if (theNewDelta < MinDelta)

\{

MinDelta = theNewDelta;

for (int j = i + 1; j <= N; j++)

\{

Exsits\[j - 1\] = false;

\}

CopyResult(Exsits, N);

\}

if (i < N)

\{

FindDouble(A, Exsits, N, M, i + 1, theCurrSum,false);

FindDouble(A, Exsits, N, M, i + 1, theCurrSum,true);

\}

\}

private void CopyResult(bool\[\] Exsits, int N)

\{

for (int i = 0; i < N; i++)

\{

Exist\[i\] = Exsits\[i\];

\}

\}

private void button3\_Click(object sender, EventArgs e)

\{

double\[\] A = new double\[\] \{1.5,2.5,3.0,5.0,8.0,9.0\};

bool\[\] E = new bool\[\] \{ false, false, false, false, false, false \};

Exist = new bool\[6\];

MinDelta = double.MaxValue;

FindDouble(A, E, 6, 12, 1, 0.0, false);

FindDouble(A, E, 6, 12, 1,0.0, true);

\}

PS:原来这种递归处理是典型的背包问题，长见识了。

2011-12-01:这个算法的本质采用的是穷举法，因此时间复杂度为o(2^n),但在中间我做了一个趋势判断，可以减少计算量。其实这个问题看起来是背包问题，但其实不是背包问题，背包问题是小于限定的，但这个问题是趋近，而不是限定，所以本质上还是有不同，同时，由于目标值是实数，W-wi情况的值怎么存都是个问题。如果W是整数，还可以转化为两个限定问题，分别动态规划求解后，比较结果决定。题目中的升序排列，其实作用不大，因为题目并没有说只能连续选。其唯一的作用就是我算法中的，我可以做一个趋势判断，如果趋势由小转为大，则可以停止。

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关递归---n皇后问题

题目描述：在 n x n 的棋盘上面所有的皇后不能相互攻击，即所有的皇后既不在同一行、不在同一列，也不在同一对角线，如下图所示（以 4 x 4 的棋盘举例）： !

蔚落/ 2023年06月25日 05:00/ 0 赞/ 46 阅读

相关 Java 递归的形式、递归三要素、n的阶乘、递归搜索文件实现

递归：方法在方法中又调用了自己。直接递归：自己的方法调用自己。间接递归：自己的方法调用别的方法，别的方法又调用自己。小结: 递归是自己调用自己。

男娘i/ 2023年03月05日 03:19/ 0 赞/ 29 阅读

相关输入2个正整数m和n(m≥1，n≤10 000)，输出m ~n 之间所有的Fibonacci数｡

【问题描述】输入2个正整数m和n(m≥1，n≤10 000)，输出m ~n 之间所有的Fibonacci数｡Fibonacci数列(第一项起):1,1,2,3,5,8,1

太过爱你忘了你带给我的痛/ 2023年02月18日 08:16/ 0 赞/ 73 阅读

相关用递归的方法求s = k! + n! / m!的值

《程序设计基础实训指导教程-c语言》 ISBN 978-7-03-032846-5 p142 7.1.2 上级实训内容【实训内容5】求`s

电玩女神/ 2023年02月14日 13:07/ 0 赞/ 56 阅读

相关 N皇后递归

include<bits/stdc++.h> using namespace std; void NQueen( int k); int qu

我不是女神ヾ/ 2022年06月18日 08:47/ 0 赞/ 228 阅读

相关递归函数求n!

\include<iostream> using namespace std; int main() \{ int n; cin>>n; int jie

末蓝、/ 2022年06月06日 11:37/ 0 赞/ 272 阅读

相关递归和非递归分别实现求第n个斐波那契数

递归和非递归分别实现求第n个斐波那契数。递归： > 在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-

青旅半醒/ 2022年05月26日 11:36/ 0 赞/ 177 阅读

相关 java 递归实现N级菜单

算法已经改进，请看最新：[https://blog.csdn.net/u011060906/article/details/98942421][https_blog.csdn.

港控/mmm°/ 2022年05月22日 08:38/ 0 赞/ 259 阅读

相关 c语言编程（递归问题）-Ackermann函数ack(m,n)

c语言编程（递归问题）-Ackermann函数ack(m,n) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

我就是我/ 2022年01月29日 10:49/ 0 赞/ 207 阅读

相关 M选n 递归编程 java_搜狗面试题：从N个正实数中选若干个数之和最接近M的递归实现...

//搜狗：有N个正实数(注意是实数，大小升序排列) x1 , x2 ... xN，另有一个实数M。 //需要选出若干个x，使这几个x的和与 M 最接近。请描述实现算法，并指

傷城~/ 2021年09月07日 06:13/ 0 赞/ 116 阅读