十年程序员难倒了一个算法上面，真的老了

以测试数据为例, 使用 dp 算法求出 3 组数据, 然后三层循环找出一个没有交集的组合

@diandian666 "不知道呢，一组数据是付款订单。另一组数据是移除订单。反正就是这两个不互通。需要自己匹配关联呢。"
so 付款订单其实是由若干商品组合成，移除的时候可能单独移除了一两个，那付款订单其实把商品 id 带上的话，这个问题会简化很多？

@lyminghao 没有任何收敛条件，全是 01 变量，这能跑出来？

@SenseHu 两组数据的订单号全部是一样的呢。只是一组有地区，另一组没地区。需要匹配成功后，也把地区填充到另一组。

OP 主楼里面的两个 case 都解出来了，正要过来 show 一下，发现 op re 的那个长 case 报“maximum recursion depth exceeded”了。

多背包问题
https://developers.google.com/optimization/bin/multiple_knapsack

不是应该先采访下人工队是怎么做的么？

我写了一个暴力解法,时间复杂度 O(n^m), n 、m 分别表示数组 1 和数组 2 的元素个数, 空间复杂度 O(m)。
两个简单例子可以跑通, 第一个例子时间复杂度约为 3.99084e+39 ，显然超时了。。。
代码如下：本来想发 gist 链接，但网站提示我像在 spamming
'''
#include<iostream>
#include<vector>
#include<list>
#include<cmath>

using namespace std;

void helper(vector<double>& arr1,int n, vector<double>& arr2, int start, int m, vector<list<double>>& res,bool& isok){
//暴力法:将 arr2 中的 m 个数分成 n 堆,编号 0~n-1 堆,堆 i 中数的和等于 arr1[i]
//对于 arr2 中的每个数有 n 中选择,放入哪个堆中,穷举加回溯
//时间复杂度为 O(n^m),空间复杂度为解空间树的深度 O(m)
if(isok) return; //isok 表示是否找到解
if(start==m) {//因为两个数组总的和相等,并且在递归过程中 arr1 数组中个数都不会<0,所以如果遍历到最后说明 arr2 中所有数都放在正确的堆中
isok = true;
return;
}
for(int i=0;i<n;++i){
if(arr1[i]>arr2[start]||fabs(arr1[i]-arr2[start])<0.00001){//arr1[i]>=arr2[start]时可以放入 arr2[start]
res[i].push_back(arr2[start]);
arr1[i] -= arr2[start];
helper(arr1,n,arr2,start+1,m,res,isok);//递归查找解
arr1[i] += arr2[start];//回溯
if(!isok) res[i].pop_back();//若未找到解则回溯
else return;//找到则直接返回
}
}
}
int main(){
// vector<double> arr1 = {62.13,26.67,17.76};
// vector<double> arr2 = {24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,
// 2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,
// 1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,
// 0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,
// 0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,
// 0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28};
//采用这组数据时,n=3,m=83,时间复杂度为 O(n^m)3.99084e+39


// vector<double> arr1 = {52.7,8.96};
// vector<double> arr2 = {21.44,6.72,5.44,5.12,4.48,3.20,2.24,1.92,1.92,1.92,1.28,
// 1.28,1.00,0.96,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32};

vector<double> arr1 = {23.17,3.2,1.22,0.32};
vector<double> arr2 = {7.36,4.16,3.20,1.69,1.28,1.28,0.96,0.96,0.90,0.64,0.64,0.64,
0.50,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32};

int n = arr1.size();
int m = arr2.size();
cout<<"len of arr1 is "<<n<<endl;
cout<<"len of arr2 is "<<m<<endl;
cout<<"n^m is "<<pow(n,m)<<endl;
vector<list<double>> res(n);
bool isok = false;
helper(arr1,n,arr2,0,arr2.size(),res,isok);
for(int i=0;i<n;++i){
cout<<arr1[i]<<":\n";
double sum = 0;
for(double j:res[i]){
cout<<j<<' ';
sum += j;
}
cout<<'\n';
bool correct = fabs(sum-arr1[i])<0.000001?true:false;//验证解法是否正确
cout<<"sum is "<<sum<<", ";
cout<<"the result is "<<(correct?"correct":"wrong")<<'\n';
}

return 0;
}
'''

我建议直接暴力穷举，因为既然人工能看的过来，不可能计算机穷举不完

额，楼主，我有个思路，不知道能不能帮到你啊。

我观察了一下你这个数据的构成。有很多形如 0.28,0.56 这种小数字。这些小数字拉高了遍历的轮次，导致你算不出来。

可不可以把这一大坨小数字，合成几个大数字，再参与你的遍历。出了结果后，再把它分解回小数字呢？

以你主题中的例子，
有 30 个 0.28 ， 要匹配 3 个数。
一个数字中的 0.28 的数量,可以表示为 2n 或者 2n+1 。 这里 2n 个 0.28 ，可以转成 n 个 0.56 。
根据鸽笼原理，3 个数，我们留 3 个 0.28 参与最后的匹配，剩下的 27 个 0.28 ，都换成 0.56 。

同样的，2n 个 0.56 可以换成 n 个 1.12...

这样参与最终匹配的数字降下来，你这个问题就能找出解。

找出解以后，你再还原回去。

@optional 啥叫收敛条件... 搜索空间有限可数，肯定能跑出来啊

我觉得你可能漏了一些业务信息，这些数字靠人工很难凑出来的

第一步：
在 a0 - an 个 数中：(A + B + C) = (a0 + ...+ a100) 得到子集合 (an + ... + am) ... (an1 + ... am1)
第二步约束：
(A + B) = (an + ... + am) && C = an1 + ... + am1
(A + C) = (an + ... + am) && B = an1 + ... + am1
(B + C) = (an + ... + am) && A = an1 + ... + am1

是不是这样？
https://paste.ubuntu.com/p/R3W7vqkfjv/

我还没开始减枝优化，发现基本上暴力都秒解。加了点小优化

写了一个,三个都能很快跑出来,是穷举优化了下.
https://gist.github.com/quxiaowei/ccb676bf2b66a4b0f9a35b959e0e7d09

@quxw 的版本能行，就是算的太慢，风扇起飞。
加上 cache 后，秒出结果。给递归加 cache ，常见的优化策略。

https://gist.github.com/4ft35t/814b5ba8bba6cf1a2fc3dc14db818cb9

@optional 数组 1 用 i 索引，数组 2 用 j 索引，xij 为整数变量，表示数组 1 元素的加和中用到了 xij 个数组 2 的 j 元素！约束条件为数组 2 元素数量约束，即数组 2 中的元素数量限制！目标函数你可以用数组 1 的表示值和真实值误差最小

@superhxl 我看的懂你的模型，不用解释，关键是这个模型本质上就是暴搜，数量稍微大点，出不来的。

@optional m*n 个变量，每个变量两个状态，复杂度是 2^（ m*n ）

因为没有唯一解（最优解）所以不大会考虑直接用动态规划思路，
于是考虑暴力搜索 dfs 、bfs 加 剪支。