algorithm - 号码形成

给定三个整数x，y和z，你需要求出4个atmost x倍、5个atmost y倍和6个atmost z倍的数字之和。
注：数字只能包含4、5、6位数字。
如：
11月1日
输出：
3675个
说明：
输入的ans是
4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675
我试着提出一个dp方法，类似于我们在寻找丑陋的数字时所做的。但没有希望？
如何解决这个问题？
我认为这是一个非常困难的问题。它是？

最佳答案

这个问题有一个简单的两部分解决方案。
你需要：
一种查找数组所有不同顺序的算法。
一种创建数组的算法，其中感兴趣的数字包含不同的次数。
对于（1）您可以将std::next_permutation()与unordered_set一起使用。
对于（2），可以构建构造数组的递归函数。
以下程序完成此操作：

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

//Convert an array of digits into an integer
int VecToNumber(const std::vector<int> &to_permute){
  int num   = 0;
  int tens  = 1;
  for(int i = to_permute.size()-1;i>=0;i--,tens*=10)
    num+=to_permute[i]*tens;
  return num;
}

void Permuter(std::vector<int> to_permute, std::vector<int> &numbers_to_add){
  //Sorting is a necessary step before we can use `std::next_permutation`
  std::sort(to_permute.begin(),to_permute.end());
  //Loop through every permutation of `to_permute`
  do {
    numbers_to_add.push_back(VecToNumber(to_permute));
  } while(std::next_permutation(to_permute.begin(), to_permute.end()));
}

//Build an array to permute
void Builder(
  const std::vector<int> &values,   //Digits to use
  const std::vector<int> &counts,   //Maximum times to use each digit
  std::vector<int> &to_permute,     //Current array
  std::vector<int> &numbers_to_add, //Numbers we will be adding
  int pos                           //Digit we are currently considering
){
  //Since to_permute is used at each level of recursion, we must preserve it
  //at each level so we can reverse the effects of deeper levels of
  //recursion when moving back to shallower levels.
  const auto original_tp = to_permute;

  if(pos<values.size()){
    //Add more and more copies of a digit to the `to_permute` array, up to
    //the value specified by `counts[pos]`
    for(int i=0;i<counts[pos];i++){
      Builder(values,counts,to_permute,numbers_to_add,pos+1);
      to_permute.push_back(values[pos]);
    }
    Builder(values,counts,to_permute,numbers_to_add,pos+1);
  } else {
    //We've run out of digits to consider, now we will generate all of the
    //permutations of those digits
    Permuter(to_permute,numbers_to_add);
  }
  to_permute = original_tp;
}

int main(){
  std::vector<int> values = {{4,5,6}}; //Digits to use
  std::vector<int> counts = {{1,1,1}}; //Maximum number of times to use each digit

  std::vector<int> to_permute;     //Holds numbers we are currently permuting
  std::vector<int> numbers_to_add; //Holds numbers that we wish to add together

  //Collect all numbers we want to add together
  Builder(values,counts,to_permute,numbers_to_add,0);

  for(auto x: numbers_to_add)
    std::cout<<x<<std::endl;

  std::cout<<"Sum = "<<std::accumulate(numbers_to_add.begin(),numbers_to_add.end(),0)<<std::endl;
}

输出：

关于algorithm - 号码形成，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45378853/