输入描述：
1、数字n，值为100倍数，范围为100～1000万。
2、数组s，包含20个元素，s=[1000，1500，2000，2500，………，10000，10500]（元素为1000～10500内值为500倍数的所有整数）。
3、数组a，包含5个元素，a=[a1,a2,a3,a4,a5]，a1～a5均为1～100之内的整数。
问题描述：
1、有一个5列3行的网格grid，初始每格数字均为0，每个格子可重新填入一个数字。现要求从数组s中任意选择8～15个数字（可每次选择相同数字）填入网格（填入位置随意），填完后的每列数字之和记为c1～c5，要求c1xa1+c2xa2+c3xa3+c4xa4+c5xa5=m=n，求满足条件的填充组合。
2、若没有满足条件的组合，则输出最接近n的一种组合，要求该组合计算出的值m不大于n，若数字m有多种组合，随机输出一种。
3、若有多种可能组合，从所有组合中随机输出一种，即保证相同的输入，有概率获得不同输出。
4、若没有满足条件和接近的组合，grid返回全0数组，m返回0。
5、要求时间复杂度不超过O(n^2)（1s至少可以处理1w次输入）。
6、内存空间限制1M。
输出描述：
1、输出填充后的网格数组grid。
2、输出实际的数字m。
这里前提是已知了n,s,a 。 怎么选8-15个数字以什么位置填入网格可以使得计算结果最接近n ？
还是已知n,s,a 和8-15个数字选完后。 怎么放使得计算结果最接近n？
比如：
输入n=78500，
a=[1,3,5,2,2],
s=[1000,1500,2000,...,10500]，
可能的返回1:
grid=[
[1000,0,1000],
[2000,1000,3000],
[2500,1500,3500],
[1000,2000,3500],
[3000,0,1000]
],
m=78500;
可能的返回2:
grid = [
[0,0,0],
[2000,1000,3000],
[2500,1500,3500],
[1000,2000,3500],
[3000,1000,1000]
],
m=78500;
很明显，还有很多种满足条件的组合，保证相同输入可以随机返回一种。
（grid每列和与a对应列相乘，然后再累加就是m。）
有概率获得不同输出，这个是古典概型？
n分解成m个正数和所有组合
类似的，可以看看
std::vector<std::vector<int> > Permute::sumNToDst(int dst, int n)
{
std::vector<std::vector<int> > r;
findUpSeq(1,n,dst,r);
std::cout<<r.size()<<" solutions "<<std::endl;
for(int i=0;i<r.size();i++){
for(int j=0;j<r.at(i).size();j++){
std::cout<<r.at(i).at(j)<<" ";
}
std::cout<<std::endl;
}
}
/**
* @brief Permute::findUpSeq
* @param low 盒子中最少放置的球数
* @param num 盒子数
* @param sum 球总数
* @param result 返回二维数组分配结果
* @return 是否分配成功
*/
int Permute::findUpSeq(int low, int num,int sum, vector<vector<int> > &result)
{
result.clear();
if(num<1||sum<0)
return 0;
//只有一个盒子
if(num==1){
if(sum>=low){
std::vector<int> v;
v.push_back(sum);
result.push_back(v);
return 1;
}
return 0;
}else if(num<1){
return 0;
}
//球数少于每个盒子应放总数之和
if(sum<num*low)
return 0;
else if(sum == num*low){
std::vector<int> t;
t.assign(num,low);
result.push_back(t);
return low;
}
std::vector<std::vector<int> > s;
//依次给1号盒子放1-n/m个球，将剩下的球放到剩下的盒子中且保证后续盒子球数不低于前一盒子
for(int i=low;((i*num)<sum+1);i++){
s.clear();
//如果后续盒子放置成功，将其放置方案中加入1号盒子中所放球数做为一个方案
if(findUpSeq(i,num-1,sum-i,s)){
for(int j=0;j<s.size();j++){
s.at(j).push_back(i);
result.push_back(s.at(j));
for(int k=0;k<s.at(j).size();k++){
std::cout<<" "<<s.at(j).at(k);
}
}
std::cout<<std::endl;
}
}
return 1;
}
第一个：想到了一个大大降低循环次数的方法，但是如果要得出精确值还是得很大循环。
第二个：还有一个降维的方法，求估值
算精确值的思路大概这样，看能不能结合题主的查表:
第1步. 数组s，包含20个元素，除以500降数值到s1
s= [1000，1500，2000，2500，………，10000，10500]
s1 = [2,3,4,5,6,.....21]
第2步. 把3行5列的格子整合起来看，3个格子单独组合虽然有8000种，但是3个格子加起来最多只有2-63种，大概60种组合，有可能更小可以预先算好，
第3步. 把5个列p5的大概60种组合和c1 c2 ... c5循环算出精确值d5 刚好为n，或者差不多的
第4步. 通过d5来确认每一列的3个数
降维估计的方法如下：
第1步：把c1，c2，c3，c4，c5按照从小到大的顺序进行排序
第2步：把a1-a2-a3-a4-a5，可以分层2组或者3组或者4组，比如如果2组 第一组为a1=a2=a3,第二组为a4=a5
第3步：那么如果是2组就降维成了（c1+c2+c3)*a1和（c4+c5)*a4， 这样就是60 * 60的复杂度
第4步：上面算出来有误差，需要精度补齐，因为c1到c5是从小到大排列了，所有一个步长c1最小，c5最大，
所以先从c5开始补齐，直到补齐到c1进行补数，找到最接近的值
第5步：把上面算出来的a1-a5分解到每一个格子
还可以降维到3维，4维等，然后精度降为 |n-m| < delta
降维的可以多想想
package com.yctx;
import java.util.*;
public class Test {
public static Map<Integer, String> numMap = new HashMap<>();
public static List<Integer> alist = new ArrayList<>();
public static List<List<Integer>> agreplist = new ArrayList<>();
public static Boolean end = false;
public static void main(String[] args) {
List<Integer> s = new ArrayList<>();
s.add(0);
//统一÷500
for (int i = 2; i <= 21; i++) {
s.add(i);
}
System.out.println(s);
// 获取所有c1 可能的值与组合
for (Integer num1 : s) {
for (Integer num2 : s) {
for (Integer num3 : s) {
numMap.put(num1 + num2 + num3, (num1 * 500) + "_" + (num2 * 500) + "_" + (num3 * 500));
}
}
}
System.out.println(numMap.size());
System.out.println(numMap);
List<Integer> a = new ArrayList<>();
a.add(1);
a.add(3);
a.add(5);
a.add(2);
a.add(2);
alist.addAll(a);
int p[] = {1, 3, 5, 2, 2};
perm(p, new Stack<>());
Integer n = 78400;
Integer m = n / 500;
end = false;
for (int j = m; j >= 0; j--) {
if (!end) {
getnum(j);
}
}
}
public static void getnum(int m) {
//将c1xa1+c2xa2+c3xa3+c4xa4+c5xa5=m
/**
* 将c1xa1+c2xa2+c3xa3+c4xa4+c5xa5=m 简化
* a+b+c+d+e=m 由于 从数组s中任意选择8～15个 设a_e 降序排列知
* 极限状态为 m-2,1,1,0,0
*/
System.out.println("m:" + (m*500));
List<Integer> numList = new ArrayList<>();
int x = 0;
for (int a = m - 2; a > 1; a--) {
if (!isNum(a)) {
continue;
}
for (int b = m - a - 1; b > 0; b--) {
if (!isNum(b) || a < b) {
continue;
}
for (int c = m - a - b; c > 0; c--) {
if (!isNum(c) || b < c) {
continue;
}
for (int d = m - a - b - c; d >= 0; d--) {
if (!isNum(d) || c < d) {
continue;
}
int e = m - a - b - c - d;
if (d < e) {
continue;
}
numList.clear();
// System.out.println("a:" + a + " b:" + b + " c:" + c + " d:" + d + " e:" + e + " sum:" + (a + b + c + d + e));
numList.add(a);
numList.add(b);
numList.add(c);
numList.add(d);
numList.add(e);
List<Integer> alist = getgroup(numList);
if (alist != null) {
System.out.println("a:" + a + " b:" + b + " c:" + c + " d:" + d + " e:" + e + " sum:" + (a + b + c + d + e));
System.out.println("alist " + alist);
System.out.println(a / alist.get(0) + "*" + alist.get(0) + "+" + b / alist.get(1) + "*" + alist.get(1) + "+" + c / alist.get(2) + "*" + alist.get(2) + "+" + d / alist.get(3) + "*" + alist.get(3) + "+" + e / alist.get(4) + "*" + alist.get(4));
System.out.println(numMap.get(a / alist.get(0)));
System.out.println(numMap.get(b / alist.get(1)));
System.out.println(numMap.get(c / alist.get(2)));
System.out.println(numMap.get(d / alist.get(3)));
System.out.println(numMap.get(e / alist.get(4)));
end = true;
return;
}
}
}
}
}
}
/**
* 如果 当前值等于 a*c 返回true
*
* @param num
* @return
*/
public static boolean isNum(int num) {
// System.out.println("-----"+num);
for (Integer num1 : alist) {
if (num % num1 == 0 && numMap.containsKey(num / num1)) {
return true;
}
}
return false;
}
/**
* a:125 b:16 c:10 d:3 e:3 sum:157
*
* @param numList
* @return
*/
public static List<Integer> getgroup(List<Integer> numList) {
for (List<Integer> alist : agreplist) {
boolean t = false;
for (int i = 0; i < 5; i++) {
if (numList.get(i) % alist.get(i) == 0 && numMap.containsKey(numList.get(i) / alist.get(i))) {
} else {
t = true;
}
}
if (!t) {
System.out.println(alist);
return alist;
}
}
return null;
}
/**
* 获取 a全排列
* @param array
* @param stack
*/
public static void perm(int[] array, Stack<Integer> stack) {//利用循环递归，将数据存入栈中
if (array.length <= 0) { //创造递归结束条件
//进入了叶子节点，输出栈中内容
Stack<Integer> stackcopy = (Stack<Integer>) stack.clone(); //克隆一个栈stackcopy，用于对栈进行相关操作，而不改变原栈内容
int length = stack.size();
Integer a[] = new Integer[length]; //定义一个长度为栈的长度的数组，用于存储栈的内容
for (int j = 0; j < length; j++) {
a[j] = stackcopy.peek(); //先取出栈顶元素到数组
stackcopy.pop(); //然后将栈顶元素出栈
}
//判断数组是否满足条件
// System.out.println(Arrays.toString(a));//该数组满足条件，打印输出满足条件的数组
List<Integer> list = Arrays.asList(a);
agreplist.add(list);
// list.addAll(a);
} else {
for (int i = 0; i < array.length; i++) { //后续就是tempArray.length
//tmepArray是一个临时数组
//例如：1，2，3的全排列，先取出1，那么这时tempArray中就是2，3
int[] tempArray = new int[array.length - 1];//以a[i]为界线，tempArray存储a[i+1]~a[array.length-1]的数据
System.arraycopy(array, 0, tempArray, 0, i);
System.arraycopy(array, i + 1, tempArray, i, array.length - i - 1);
stack.push(array[i]);//1;array[i]依次入栈
perm(tempArray, stack); //递归,tempArray相对于array
stack.pop(); //栈顶元素出栈，还原array数组，以便进行下一次循环的操作
}
}
}
}
m=n看标题就知道都是1😂