求和问题！

unknowno

已知若干个自然数，例如：[12,34,56,3,4,15,67,90,34,23,78,44,87,32,5,67,33]

其中任意组合数值相加，如何找出总和最接近50的一个组合。

friendchj

一个思路，找出所有小于50的元素的集合，求其所可能组合的和。

VibrationMaster

SumTarget=50;
X=[12,34,56,3,4,15,67,90,34,23,78,44,87,32,5,67,33]
CloseMost=+Inf;
for k1=1:length(X)
     for k2=k1+1:length(X)
          if(abs(X(k1)+X(k2)-SumTarget)<CloseMost)
               CloseIndex=[k1,k2];
          end
      end
end
% CloseIndex save what you want

[ 本帖最后由 VibrationMaster 于 2009-8-6 15:15 编辑 ]

ChaChing

X=[12,34,56,3,4,15,67,90,34,23,78,44,87,32,5,67,33];
aa=nchoosek(X,2); [mm,ii]=min(abs(sum(aa,2)-50));
aa(ii,:)

[ 本帖最后由 ChaChing 于 2009-8-9 20:48 编辑 ]

friendchj

以上方法只考虑两个元素之和的情况，还有可能一个元素或3个之和、……更接近50，参考楼上的方法

ChaChing

真的老了, 记性越来越差!
看完VibrationMaster的方式, 就是感觉不够通用性(若多个即需多个loop), 才试作的!
赶时间竟仅复制程序忘记说明! 还好friendchj够仔细, 谢谢!

unknowno

结果好像不对呀，最接近50的组合可能是2个或3个或更多数值

ChaChing

原帖由 unknowno 于 2009-8-6 08:45 发表

                               
登录/注册后可看大图

...如何找出总和最接近50的一个组合。

到底是一个组合或所有组合?
刚刚才发现4F有个错误, 可能复制错了! sorry!
所有组合
X=[12,34,56,3,4,15,67,90,34,23,78,44,87,32,5,67,33];
aa=nchoosek(X,2); aad=abs(sum(aa,2)-50); mm=min(aad); ii=find(aad==mm); aa(ii,:)

friendchj

写了一个程序，可以参考一下[第一次寻找最小值时用了min，只取第一个min值，考虑到重复情况，可以用find代替min]：
clc
clear
x=[12,34,56,3,4,15,67,90,34,23,78,44,87,32,5,67,33];
% 寻找小于50的元素集合
x=sort(x);
for i=1:length(x)
    if x(i)>50
        break;
    end
end
x1=x(1:i-1);
% 寻找各种情况下的组合最小值
index=zeros(2,length(x1));
for i=1:length(x1)
    s=nchoosek(x1,i);
    [m,ind]=min((abs(sum(s,2)-50)));
    index(1,i)=ind;
    index(2,i)=m;
end
% 求各种情况下的组合最小值的最小值
ind=find((index(2,:)-min(index(2,:)))==0);
for i=1:length(ind)
    s=nchoosek(x1,ind(i));
    disp(s(index(1,ind(i)),:))
end
%%%%%%%%%%%%
     3    15    32
     3     4     5    15    23

[ 本帖最后由 friendchj 于 2009-8-10 18:36 编辑 ]

ChaChing

"总和最接近50"的元素一定要小於50吗?

friendchj

这个不一定，所以在第一步提取所有小于50的元素集合，严格来说是有问题的。针对这个问题取小于50不成问题，换成其他的情况应该考虑一下。元素越少，运算量也越小。