simple_solution.cpp

#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;
}