随机选择

请你分享你的想法就以下问题随机选择

假设你有一个像

Data=[ a1 a2 a3 a4..... an]; 0<ai<100

1-d矢量数据，我们怎么能找到数据的子集如

Data_subset=[ a3 a7 a8] or Data_subset=[ a1 a17 a81 a92 a93 a100 a101 ]

其最好保持这种状态：abs(sum(Data_subset)-700)<10

任何ID EA？

来源

2016-07-06 Karlo Gonzales

这似乎是非常相似的[背包问题]（https://en.wikipedia.org/wiki/Knapsack_problem），这是已知很难准确解决 –

我会称之为[子集合问题]（https://en.wikipedia.org/wiki/Subset_sum_problem）。 – beaker

当你说“哪一个最好保存这个条件”时，你的意思是你希望任何将abs（sum（Data_subset）-700）<10'保持为真的子集，或者你想要那些具有最小值“ ABS（SUM（Data_subset）-700）'？ –

可以通过

（^ 2 + N-1）/ 2（（N-1））+ N 从N = 1到N

唯一=总和计算唯一子集（忽略顺序）的数量= 99

所以，如果你只需要为长度为100的矢量做这件事，你将只有166750个独特的数据子集。在这种情况下，你应该没有问题通过测试每个子集强制问题，也就是说，如果你可以创建一个方法来生成它们。

你可以使用类似matlab函数perms（）的东西，它会给你所有向量的排列，除了你应该像1e156不同的排列。

的只是局部的解决方案，我能想到的是使用randperm（），然后创建一个循环测试是随机排列

nPerms = 100 
    subSetsSaved = cell() 
    cellIndex=1; 
    for iRand=1:1:nPerms 
     randOrder = randperm(length(data)); 
     dataPerm = permute(data,randOrder); 
     for jSub=1:1:length(data) 
       subSet = dataPerm(1:jSub); 
       if (abs(sum(subSet)-700)<10) 
        subSetsSaved{cellIndex} = subSet; 
        cellIndex = cellIndex+1; 
       end 
      end 
    end

的子集，你甚至可以使用这个随机排列循环试图随机生成全部166750个独特的子集。你所要做的就是随机生成，排序和测试唯一性。当然，这些解决方案在效率方面并不理想，所以如果这是一个问题，您需要快速解决问题，或者如果您的设备比N = 100大得多，则需要采用不同的方法。

来源

2016-07-07 14:06:44 blindpanic

我不确定我理解你对唯一子集数量的计算。从我可以看到它是二进制的：每个元素或者在子集中或者不在，所以唯一子集的数量是'2^n'，其中'n'是原始矢量的长度。 – beaker

回答

相关问题