Created
November 16, 2022 08:38
-
-
Save KeenNjupt/ec831603f46a95db06b71c13f828e108 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment