宝石分配问题

本文主要是介绍宝石分配问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把M个同样的宝石放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？(其中1，5，1和5，1，1代表同一种方法)，用C++实现
注意最后是输出n行字符，不是算出来有几种分法。假设输入为7, 3
示例:
如输入7，3，输出为8行：
7，0，0
6，1，0
5，2，0
4，3，0
5，1，1
4，2，1
3，3，1
3，2，2

答案是：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>using namespace std;string vectorToString(vector<int> partitions)
{string res;for(int i = 0; i < partitions.size(); ++i){res += to_string(partitions[i]);if(i != partitions.size() - 1){res += ",";}}return res;
}void generatePartitions(int gems, int plates, vector<int>& partitions, set<string, greater<string>>& uniquePartitions) {if (plates == 1) {partitions.push_back(gems);vector<int> tempPartitions = partitions;sort(tempPartitions.begin(), tempPartitions.end(), [](int a, int b){return a > b;});uniquePartitions.insert(vectorToString(tempPartitions));partitions.pop_back();return;}for (int i = 0; i <= gems; ++i) {partitions.push_back(i);generatePartitions(gems - i, plates - 1, partitions, uniquePartitions);partitions.pop_back();}
}int main() {int gems = 7;  // 宝石的数量int plates = 3;  // 盘子的数量vector<int> partitions;set<string, greater<string>> uniquePartitions;generatePartitions(gems, plates, partitions, uniquePartitions);// 打印所有不重复的分割for (const auto& partition : uniquePartitions) {cout << partition << endl;}return 0;
}

输出是：

7,0,0
6,1,0
5,2,0
5,1,1
4,3,0
4,2,1
3,3,1
3,2,2

这篇关于宝石分配问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---