[讨论]找出集合中求和是原集合一半的子集合

qibbxxt

题目来自Cody,就是找出集合的子集，使得子集的和为原集合的一半

1. Given a vector x, return the indices to elements that will sum to exactly half of the sum of all elements.
   
2. 
   
3. Example:
   
4. 
   
5. Input  x  = [1 2 3 4 5 6 7]
   
6. Output xi = [1 6 7]
   
7. because
   
8. 
   
9. sum(x) = 28
   
10. sum(x([1 6 7])) = 14
    
11. The answer is not necessarily unique and the order is unimportant. We will just test to make sure that sum(x)/2 is sum(x(xi))

复制代码

以下是测试函数

1. 1
   
2. %%
   
3. x = [1 2 3 4 5 6 7];
   
4. xi = split_it(x);
   
5. assert(isequal(sum(x(xi)),sum(x)/2));
   
6. 
   
7. 2
   
8. %%
   
9. x = [2 2 2 2 2 2];
   
10. xi = split_it(x);
    
11. assert(isequal(sum(x(xi)),sum(x)/2));
    
12. 
    
13. 3
    
14. %%
    
15. x = [2     5     4     5     4];
    
16. xi = split_it(x);
    
17. assert(isequal(sum(x(xi)),sum(x)/2));
    
18. 
    
19. 4
    
20. %%
    
21. x = [1     3     1     1     9     7];
    
22. xi = split_it(x);
    
23. assert(isequal(sum(x(xi)),sum(x)/2));
    
24. 
    
25. 5
    
26. %%
    
27. x = primes(100);
    
28. xi = split_it(x);
    
29. assert(isequal(sum(x(xi)),sum(x)/2));

复制代码

希望大家一起讨论

原题目链接：http://www.mathworks.cn/matlabcentral/cody/problems/660-find-a-subset-that-divides-the-vector-into-equal-halves

liuyalong008

还是有难度的，首先个人觉得全遍历组合可能会比较慢，给出随机数组合的solution：

1. function ans= split_it(x)
   
2. len=length(x)
   
3. d=randi(len,[10000,fix(len/2)]);
   
4. idx = arrayfun(@(i)sum(x(unique(d(i,:)))),1:length(d))'==sum(x)/2;
   
5. find(idx,1,'first')
   
6. unique(d(ans,:))
   
7. end

复制代码

rocwoods

我也是用的随机的方法。

1. 
   
2. function ans = split_it(x)
   
3. ind = 1:length(x);
   
4. while ~any(cumsum(x(ind))==sum(x)/2)
   
5.     ind = randperm(length(x));      
   
6. end
   
7. ind(1:find(cumsum(x(ind))==sum(x)/2,1,'first'));
   
8. end
   
9. 
   

复制代码

qibbxxt

求解方程的方法

1. function ans = split_it(x)
   
2. bintprog([],[],[],x,sum(x)/2);

复制代码

rocwoods

size改进到32了。

1. function ans = split_it(x)
   
2. while 1
   
3.     randi(2,length(x),1);
   
4.     if diff(accumarray(ans,x(:)))
   
5.     else
   
6.         ans==1;
   
7.         break
   
8.     end   
   
9. end

复制代码

qibbxxt

rocwoods 发表于 2013-12-25 18:06
size改进到32了。

稍加修改

1. function ans = split_it(x)
   
2. while 1
   
3.     randi(2,length(x),1);
   
4.     if diff(accumarray(ans,x(:))) == 0
   
5.         ans == 1;
   
6.         break
   
7.     end   
   
8. end

复制代码

qibbxxt

1. function ans = split_it(x)
   
2. x;
   
3. while x * ans'
   
4.    randsrc(1,length(x));
   
5. end
   
6. ans == 1;

复制代码

nwcwww

随机：

1. function ans = split_it(x)
   
2.    while 1
   
3.             length(x);
   
4.             randperm(ans, randi(ans));
   
5.             if sum(x(ans))==sum(x)/2
   
6.                   break
   
7.             end
   
8.    end
   
9. end

复制代码

遍历：

1. function ans = split_it(x)
   
2.       for  k = 0:2^length(x)-1
   
3.               find(dec2bin(k, length(x))-'0');
   
4.               if(sum(x(ans))==sum(x)/2)
   
5.                        break
   
6.               end
   
7.      end
   
8. end

复制代码