时间戳

首页 > 解决方案 > 3组列表中最佳总和组合的算法

r - 3组列表中最佳总和组合的算法

问题描述

我有多组数据，例如：

X <-  c(2,3,5,10,15) 
Y <- c(4,6,23,15,12) 
Z <- c(23,34,12,1,5)

和一个目标：target = 50

我想知道最好的（例如）：来自 X 的 2 个值（称为 X2），来自 Y（Y4）的 4 个值和来自 Z（Z3）的 3 个值，如果我将它们相加，我会得到sum(X2) + sum(Y4) + sum(Z3) = 50（或最接近 50） .

这个问题有解决方案吗？

编辑：我提供的数据只是一个例子……我的最终目标是在大数据上重现它。

这是我的大数据：


target <- 362007 

X <- c(1782L, 1780L, 1783L, 1784L, 1783L, 1781L, 1782L, 1781L, 1782L, 
1782L, 1782L, 1784L, 1780L, 1784L, 1782L, 1779L, 1782L, 1784L, 
1783L, 1782L, 1781L, 1777L, 1784L, 1782L, 1784L, 1784L, 1784L, 
1782L, 1784L, 1782L, 1783L, 1783L, 1785L, 1782L, 1781L, 1782L, 
1788L, 1789L, 1786L, 1787L, 1786L, 1783L, 1781L, 1781L, 1786L, 
1787L, 1786L, 1786L, 1785L, 1785L, 1784L, 1786L, 1785L, 1784L, 
1786L, 1785L, 1785L, 1783L, 1787L, 1787L, 1786L, 1785L, 1788L, 
1786L, 1788L, 1786L, 1780L, 1788L, 1785L, 1784L, 1786L, 1784L, 
1785L, 1783L, 1785L, 1785L, 1785L, 1786L, 1784L, 1784L, 1785L, 
1784L, 1785L, 1787L, 1786L, 1788L, 1785L, 1785L, 1780L, 1787L, 
1784L, 1785L, 1787L, 1784L, 1780L, 1785L, 1782L, 1787L, 1786L, 
1781L, 1780L, 1784L, 1785L, 1785L, 1785L, 1785L, 1785L, 1782L, 
1783L, 1787L, 1784L, 1783L, 1783L, 1782L, 1785L, 1783L, 1783L, 
1782L, 1786L, 1783L, 1786L, 1782L, 1783L, 1786L, 1784L, 1782L, 
1782L, 1785L, 1785L, 1783L, 1782L, 1781L, 1782L, 1779L, 1781L, 
1781L, 1785L, 1780L, 1782L, 1781L, 1782L, 1786L, 1786L, 1787L, 
1781L, 1780L, 1788L, 1781L, 1781L, 1780L, 1787L, 1787L, 1787L, 
1780L, 1786L, 1786L, 1779L, 1785L, 1792L, 1788L, 1781L, 1784L, 
1780L, 1784L, 1783L, 1785L, 1783L, 1783L, 1781L, 1783L, 1785L, 
1783L, 1785L, 1782L, 1785L, 1782L, 1782L, 1782L, 1779L, 1787L, 
1784L, 1783L, 1783L, 1786L, 1785L, 1787L, 1785L, 1783L, 1783L, 
1786L, 1784L, 1778L, 1787L, 1786L, 1784L, 1784L, 1781L, 1779L, 
1782L, 1786L, 1781L, 1787L, 1783L, 1781L, 1781L, 1786L, 1787L, 
1780L, 1779L, 1785L, 1784L, 1781L, 1783L, 1782L, 1781L, 1781L, 
1787L, 1785L, 1787L, 1784L, 1784L, 1783L, 1782L, 1785L, 1785L, 
1783L, 1779L, 1786L, 1780L, 1778L, 1783L, 1785L, 1780L, 1786L, 
1784L, 1779L, 1779L, 1779L, 1785L, 1780L, 1786L, 1778L, 1782L, 
1779L, 1779L, 1784L, 1780L, 1780L, 1785L, 1781L, 1778L, 1787L, 
1781L, 1786L, 1783L, 1784L, 1785L, 1786L, 1784L, 1782L, 1784L, 
1785L, 1786L, 1786L, 1785L, 1782L, 1786L, 1783L, 1783L, 1788L, 
1779L, 1786L, 1787L, 1781L, 1780L, 1780L, 1782L, 1784L, 1787L, 
1780L, 1786L, 1786L, 1786L, 1784L, 1787L, 1785L, 1784L, 1784L, 
1784L, 1781L, 1784L, 1784L, 1786L, 1784L, 1783L, 1784L, 1786L, 
1787L, 1786L, 1786L, 1785L, 1786L, 1785L, 1785L)

Y <- c(1786L, 1786L, 1786L, 1786L, 1787L, 1784L, 1782L, 1787L, 1786L, 
1786L, 1781L, 1787L, 1782L, 1785L, 1785L, 1786L, 1783L, 1781L, 
1787L, 1780L, 1785L, 1783L, 1787L, 1785L, 1786L, 1789L, 1784L, 
1785L, 1782L, 1780L, 1783L, 1786L, 1784L, 1782L, 1781L, 1788L, 
1785L, 1779L, 1782L, 1781L, 1781L, 1785L, 1781L, 1786L, 1784L, 
1782L, 1783L, 1782L, 1783L, 1784L, 1786L, 1780L, 1784L, 1782L, 
1779L, 1783L, 1789L, 1783L, 1782L, 1786L, 1784L, 1783L, 1788L, 
1786L, 1788L, 1783L, 1785L, 1787L, 1787L, 1784L, 1784L, 1787L, 
1783L, 1782L, 1787L, 1788L, 1786L, 1786L, 1785L, 1787L, 1782L, 
1787L, 1782L, 1787L, 1783L, 1787L, 1783L, 1784L, 1782L, 1782L, 
1784L, 1784L, 1786L, 1782L, 1780L, 1786L, 1783L, 1787L, 1785L, 
1786L, 1783L, 1783L, 1780L, 1781L, 1782L, 1788L, 1782L, 1783L, 
1785L, 1785L, 1783L, 1786L, 1785L, 1786L, 1780L, 1782L, 1785L, 
1784L, 1787L, 1779L, 1783L, 1782L, 1785L, 1780L, 1780L, 1786L, 
1782L, 1785L, 1785L, 1779L, 1783L, 1786L, 1787L, 1789L, 1782L, 
1781L, 1783L, 1780L, 1784L, 1783L, 1784L, 1784L, 1785L, 1785L, 
1786L, 1782L, 1782L, 1781L, 1783L, 1787L, 1784L, 1785L, 1782L, 
1781L, 1786L, 1784L, 1783L, 1784L, 1786L, 1784L, 1781L, 1783L, 
1786L, 1784L, 1782L, 1782L, 1786L, 1783L, 1782L, 1784L, 1786L, 
1784L, 1786L, 1783L, 1788L, 1782L, 1782L, 1787L, 1780L, 1781L, 
1782L, 1787L, 1785L, 1781L, 1781L, 1783L, 1787L, 1785L, 1786L, 
1783L, 1786L, 1780L, 1785L, 1786L, 1786L, 1781L, 1786L, 1786L, 
1787L, 1786L, 1783L, 1789L, 1785L, 1782L, 1789L, 1788L, 1784L, 
1782L, 1783L, 1781L, 1784L, 1783L, 1783L, 1787L, 1784L, 1783L, 
1781L, 1783L, 1787L, 1783L, 1786L, 1791L, 1782L, 1788L, 1786L, 
1785L, 1782L, 1787L, 1782L, 1784L, 1782L, 1782L, 1781L, 1782L, 
1784L, 1783L, 1783L, 1784L, 1780L, 1787L, 1783L, 1785L, 1782L, 
1786L, 1782L, 1787L, 1785L, 1782L, 1785L, 1784L, 1786L, 1783L, 
1781L, 1782L, 1781L, 1785L, 1782L, 1783L, 1784L, 1782L, 1782L, 
1784L, 1783L, 1787L, 1786L, 1786L, 1781L, 1782L, 1785L, 1787L, 
1784L, 1782L, 1788L, 1782L, 1783L, 1783L, 1785L, 1781L, 1780L, 
1786L, 1785L, 1780L, 1781L, 1782L, 1787L, 1784L, 1780L, 1782L, 
1781L, 1781L, 1780L, 1784L, 1782L, 1792L, 1787L, 1782L, 1779L, 
1784L, 1785L, 1786L, 1782L, 1786L, 1785L, 1785L, 1784L, 1785L, 
1783L, 1786L, 1785L, 1783L, 1782L, 1784L, 1781L, 1782L, 1784L, 
1786L, 1783L, 1783L, 1781L, 1785L, 1779L, 1783L, 1781L, 1781L, 
1786L, 1783L, 1781L, 1787L, 1782L, 1787L, 1786L, 1645L, 1788L, 
1783L, 1786L, 1787L, 1783L, 1780L, 1781L, 1782L, 1782L, 1786L, 
1781L, 1785L, 1783L, 1784L, 1783L, 1784L, 1784L, 1781L, 1787L, 
1781L, 1785L, 1782L, 1784L, 1790L, 1795L, 1793L, 1780L, 1782L, 
1788L, 1787L, 1788L, 1781L, 1781L, 1788L, 1782L, 1783L, 1780L, 
1785L, 1784L, 1781L, 1786L, 1781L, 1787L, 1794L, 1792L, 1791L, 
1781L, 1779L, 1781L, 1781L, 1782L, 1784L, 1783L, 1785L, 1785L, 
1785L, 1781L, 1778L, 1782L, 1784L, 1786L, 1786L, 1784L, 1782L, 
1779L, 1781L, 1782L, 1785L, 1783L, 1782L, 1784L, 1779L, 1785L, 
1784L, 1787L, 1785L, 1786L, 1789L, 1788L, 1785L, 1785L, 1785L, 
1783L, 1784L, 1786L, 1784L, 1782L, 1779L, 1782L, 1787L, 1788L, 
1782L, 1786L, 1784L, 1783L, 1782L, 1785L, 1785L, 1786L, 1786L, 
1786L, 1785L, 1785L, 1789L, 1786L, 1781L, 1785L, 1784L, 1787L, 
1781L, 1788L, 1783L, 1786L, 1786L, 1786L, 1783L, 1788L, 1788L, 
1781L, 1787L, 1791L, 1784L, 1784L, 1785L, 1784L, 1784L, 1782L, 
1779L, 1777L, 1780L, 1783L, 1782L, 1780L, 1781L, 1785L, 1780L, 
1783L, 1786L, 1784L, 1779L, 1785L, 1784L, 1783L, 1783L, 1783L, 
1783L, 1785L, 1781L, 1778L, 1781L, 1785L, 1781L, 1782L, 1788L, 
1782L, 1783L, 1781L, 1786L, 1781L, 1784L, 1782L, 1783L, 1787L, 
1783L, 1786L, 1783L, 1780L, 1781L, 1779L, 1781L, 1784L, 1785L, 
1782L, 1785L, 1785L, 1783L, 1781L, 1780L, 1780L, 1781L, 1779L, 
1780L, 1783L, 1782L, 1786L, 1780L, 1785L, 1786L, 1781L, 1783L, 
1783L, 1788L, 1783L, 1786L, 1788L, 1786L, 1783L, 1784L, 1788L, 
1787L, 1785L, 1785L, 1784L, 1782L, 1785L, 1785L, 1784L, 1781L, 
1788L, 1785L, 1785L, 1786L, 1785L, 1786L, 1787L, 1781L, 1787L, 
1782L, 1781L, 1786L, 1781L, 1783L, 1782L, 1786L, 1786L, 1788L, 
1781L, 1781L, 1783L, 1784L, 1783L, 1781L, 1788L, 1785L, 1779L, 
1786L, 1781L, 1781L, 1787L, 1784L, 1788L, 1782L, 1786L, 1787L, 
1780L, 1785L, 1788L, 1783L, 1783L, 1785L, 1780L, 1780L, 1788L, 
1784L, 1782L, 1787L, 1782L, 1783L, 1782L, 1782L, 1786L, 1784L, 
1788L, 1783L, 1785L, 1786L, 1781L, 1784L, 1782L, 1792L, 1784L, 
1782L, 1780L, 1784L, 1782L, 1783L, 1785L, 1783L, 1787L, 1785L, 
1785L, 1781L, 1787L, 1785L, 1787L, 1783L, 1780L, 1780L, 1785L, 
1783L, 1786L, 1784L, 1783L, 1782L, 1782L, 1789L, 1783L, 1786L, 
1785L, 1783L, 1787L, 1788L, 1783L, 1783L, 1786L, 1783L, 1786L, 
1782L, 1787L, 1782L, 1784L, 1782L, 1786L, 1787L, 1788L, 1788L, 
1782L, 1786L, 1780L, 1785L, 1779L, 1779L, 1779L, 1779L, 1779L, 
1783L, 1783L, 1782L, 1786L, 1785L, 1783L, 1781L, 1780L, 1784L, 
1779L, 1785L, 1780L, 1779L, 1780L, 1779L, 1780L, 1782L, 1783L, 
1781L, 1785L, 1783L, 1786L, 1779L, 1781L, 1781L, 1781L, 1780L, 
1781L, 1780L, 1780L, 1780L, 1780L, 1781L, 1781L, 1781L, 1781L, 
1781L, 1781L, 1780L, 1780L, 1781L, 1786L, 1780L, 1781L, 1780L, 
1780L, 1795L, 1790L, 1793L, 1786L, 1784L, 1782L, 1784L, 1783L, 
1788L, 1787L, 1786L, 1778L, 1783L, 1786L, 1784L, 1783L, 1785L, 
1786L, 1780L, 1786L, 1786L, 1785L, 1782L, 1782L, 1786L, 1784L, 
1787L, 1789L, 1788L, 1782L, 1783L, 1787L, 1783L, 1786L, 1782L, 
1782L, 1786L, 1783L, 1785L, 1788L, 1788L, 1787L, 1783L, 1788L, 
1783L, 1782L, 1782L, 1786L, 1789L, 1784L, 1785L, 1780L, 1781L, 
1786L, 1786L, 1788L, 1785L, 1781L, 1786L, 1785L, 1782L, 1780L, 
1784L, 1781L, 1779L, 1785L, 1786L, 1779L, 1782L, 1783L, 1783L, 
1780L, 1783L, 1782L, 1786L, 1779L, 1780L, 1781L, 1786L, 1783L, 
1785L, 1786L, 1782L, 1787L, 1784L, 1786L, 1786L, 1785L, 1786L, 
1785L, 1784L, 1787L, 1784L, 1784L, 1788L, 1785L, 1784L, 1782L, 
1783L, 1785L, 1782L, 1787L, 1781L, 1782L, 1785L, 1782L, 1786L, 
1785L, 1787L, 1787L, 1786L, 1787L, 1780L, 1785L, 1784L, 1783L, 
1782L, 1787L, 1779L, 1779L, 1786L, 1780L, 1787L, 1781L, 1778L, 
1782L, 1779L, 1778L, 1780L, 1786L, 1779L, 1785L, 1784L, 1779L, 
1784L, 1781L, 1784L, 1782L, 1785L, 1783L, 1781L, 1786L, 1780L, 
1781L, 1780L, 1781L, 1784L, 1787L, 1779L, 1786L, 1781L, 1782L, 
1780L, 1782L, 1786L, 1786L, 1787L, 1782L, 1788L, 1783L, 1785L, 
1788L, 1785L, 1786L, 1787L, 1787L, 1785L, 1784L, 1784L, 1787L, 
1788L, 1787L, 1782L, 1786L, 1784L, 1783L, 1786L, 1782L, 1782L, 
1789L, 1784L, 1783L, 1793L, 1794L, 1793L, 1787L, 1783L, 1782L, 
1786L, 1784L, 1787L, 1783L, 1783L, 1786L, 1789L, 1781L, 1785L, 
1784L, 1788L, 1789L, 1782L, 1784L, 1784L, 1787L, 1787L, 1783L, 
1784L, 1784L, 1783L, 1786L, 1783L, 1785L, 1788L, 1787L, 1788L, 
1783L, 1784L, 1783L, 1783L, 1781L, 1784L, 1786L, 1782L, 1791L, 
1787L, 1781L, 1787L, 1785L, 1787L, 1783L, 1785L, 1782L, 1784L, 
1787L, 1784L, 1783L, 1783L, 1783L, 1784L, 1786L, 1787L, 1782L, 
1789L, 1782L, 1782L, 1783L, 1782L, 1783L, 1783L, 1784L, 1783L, 
1788L, 1786L, 1782L, 1784L, 1781L, 1786L, 1782L, 1779L, 1780L, 
1783L, 1780L, 1786L, 1780L, 1786L, 1784L, 1784L, 1785L, 1777L, 
1783L, 1780L, 1784L, 1783L, 1780L, 1784L, 1781L, 1785L, 1785L, 
1781L, 1780L, 1786L, 1788L, 1787L, 1791L, 1789L, 1787L, 1787L, 
1793L, 1781L, 1784L, 1781L, 1784L, 1779L, 1784L, 1784L, 1784L, 
1780L, 1780L, 1784L, 1787L, 1782L, 1781L, 1784L, 1787L, 1785L, 
1781L, 1785L, 1783L, 1782L, 1782L, 1785L, 1781L, 1782L, 1786L, 
1788L, 1780L, 1787L, 1784L, 1788L, 1787L, 1784L, 1784L, 1785L, 
1780L, 1786L, 1780L, 1780L, 1788L, 1782L, 1793L, 1783L, 1785L, 
1785L, 1781L, 1783L, 1783L, 1787L, 1783L, 1784L, 1784L, 1783L, 
1785L, 1787L, 1788L, 1784L, 1787L, 1787L, 1785L, 1786L, 1784L, 
1786L, 1784L, 1786L, 1787L)

Z <- c(1788L, 1792L, 1787L, 1791L, 1790L, 1789L, 1791L, 1788L, 1792L, 
1794L, 1793L, 1791L, 1792L, 1787L, 1792L, 1792L, 1791L, 1788L, 
1792L, 1794L, 1791L, 1788L, 1794L, 1794L, 1789L, 1792L, 1788L, 
1793L, 1792L, 1788L, 1786L, 1787L, 1791L, 1786L, 1788L, 1792L, 
1787L, 1785L, 1786L, 1790L, 1788L, 1790L, 1792L, 1788L, 1787L, 
1790L, 1786L, 1792L, 1789L, 1787L, 1786L, 1787L, 1793L, 1793L, 
1792L, 1789L, 1786L, 1795L, 1793L, 1788L, 1791L, 1790L, 1792L, 
1790L, 1794L, 1792L, 1789L, 1791L, 1794L, 1788L, 1788L, 1794L, 
1794L, 1792L, 1790L, 1789L, 1788L, 1788L, 1789L, 1789L, 1794L, 
1790L, 1787L, 1791L, 1789L, 1791L, 1790L, 1783L, 1782L, 1781L, 
1781L, 1793L, 1788L, 1795L, 1793L, 1789L, 1791L, 1793L, 1792L, 
1792L, 1784L, 1781L, 1782L, 1795L, 1788L, 1789L, 1793L, 1793L, 
1792L, 1791L, 1791L, 1790L, 1794L, 1792L, 1796L, 1793L, 1791L, 
1793L, 1790L, 1794L, 1795L, 1788L, 1789L, 1790L, 1790L, 1793L, 
1790L, 1795L, 1793L, 1792L, 1778L, 1784L, 1782L, 1791L, 1793L, 
1791L, 1794L, 1793L, 1793L, 1790L, 1792L, 1788L, 1786L, 1790L, 
1794L, 1794L, 1791L, 1787L, 1792L, 1790L, 1791L, 1799L, 1790L, 
1788L, 1795L, 1791L, 1792L, 1787L, 1788L, 1792L, 1795L, 1786L, 
1785L, 1778L, 1794L, 1790L, 1794L, 1792L, 1793L, 1793L, 1793L, 
1792L, 1791L, 1794L, 1791L, 1788L, 1789L, 1790L, 1794L, 1793L, 
1793L, 1791L, 1791L, 1795L, 1790L, 1790L, 1788L, 1793L, 1793L, 
1786L, 1788L, 1795L, 1790L, 1781L, 1781L, 1782L, 1786L, 1794L, 
1787L, 1787L, 1782L, 1786L, 1783L, 1788L, 1784L)

标签： r

解决方案

MixedCombnPerm这是一个可以在这里找到的功能的解决方案。

该解决方案包括推导所有可能的组合，然后采用最佳组合。

X <-  c(2,3,5,10,15) 
Y <- c(4,6,23,15,12) 
Z <- c(23,34,12,1,5)

set_list <- list(X, Y, Z)
k <- c(2, 4, 3)

combinations <- MixedCombnPerm(set_list, k)
total <- colSums(combinations)
deviation <- abs(total - 50)
is <- which(deviation == min(deviation))
combinations[, is]
# [1]  2  3  4  6 15 12 12  1  5
total[is]
# [1] 60

这是一个解决方案CVXR。结果中的小值实际上是 0。

library(CVXR)
x <- Bool(5)
y <- Bool(5)
z <- Bool(5)
constraintX <- sum(x) == 2
constraintY <- sum(y) == 4
constraintZ <- sum(z) == 3
objective <- Minimize((sum(x*X+y*Y+z*Z) - 50)^2)
problem <- Problem(objective, 
                   constraints = list(constraintX, constraintY, constraintZ))
result <- solve(problem)
result$getValue(x)
#              [,1]
# [1,] 1.000000e+00
# [2,] 1.000000e+00
# [3,] 1.168141e-09
# [4,] 8.964959e-11
# [5,] 2.563038e-11
result$getValue(y)
#              [,1]
# [1,] 1.000000e+00
# [2,] 1.000000e+00
# [3,] 1.841415e-10
# [4,] 1.000000e+00
# [5,] 1.000000e+00
result$getValue(z)
#              [,1]
# [1,] 9.946796e-11
# [2,] 3.816320e-11
# [3,] 1.000000e+00
# [4,] 1.000000e+00
# [5,] 1.000000e+00

编辑

这是CVXR用于大数据的解决方案。首先，安装软件包Rglpk：

install.packages("Rglpk")

然后做：

result <- solve(problem, solver = "GLPK")

我用它测试过

objective <- Minimize( abs( sum(x*X) + sum(y*Y) + sum(z*Z) - target) )

它奏效了。

推荐阅读