C++:动态规划之分组问题所有解
将若干个人(A,B,C,D,E,F,G……)分成若干队，每队人数可以是1、2或者3人。已知n，求组队详细方案例：有3个人，方案有5个，分别是全部单独组队方案 , 单独组队与双人组队方案以及三人组队方案希望各位能够给个代码或者给个思路谢谢
-
我觉得这个问题可以分几步来做。 首先考虑这么一种最简单的情形，假设有n个人，分解后每一队有且只有k个人，且n是k的倍数即n=p k。 这种情况下有多少种分组方案呢？ 应该有C(n,k) C(n-k,k) C(n-2k,k) … C(2k,k) C(k,k)/p! 然后我们考虑这样一个方程式 n=1 K1+2 K2+3*K3， 这个方程当然有好多解。对于其中的一组有效解K1,K2,K3，可以做如下分配： 先在n人中挑选出K1个人（这样的选法有C(n,K1)种）进行一人一组的分配。对于挑选好的每一种K1的集合，都有C(K1,1) *C(K1-1,1)* … C(1,1)/K1!=1种分配方案。 所以共有A(K1,K2,K3)=C(n,K1)种方案。 再在剩下的n-K1人中挑选出2 K2个人(这样的选法有C(n-K1,2*K2)种)进行2人一组的分配。对于挑选好的每一种K2的集合，都有C(n-K1,2) *C(n-K1-2,2)* … C(2,2)/K2!种分配方案 所以共有B(K1,K2,K3)=C(n-K1,2 K2)*C(n-K1,2) *C(n-K1-2,2)* … C(2,2)/K2!种方案。 最后在剩下的n-K1-2 K2人中挑选3*K3(呃不用挑选了，剩下的都是)进行3人一组的分配，对于挑选好的每一种K3的集合，都有C(n-K1-2 *K2,3) C(n-K1-2 K2-3,3)* … C(3,3)/K3!种分配方案。 所以共有C(K1,K2,K3)=C(n-K1-2 K2,3) C(n-K1-2 K2-3,3) … C(3,3)/K3!种方案。
所以我的方案是，先求出n=1 K1+2 K2+3*K3的所有整数解，然后对于每一种整数解，依次去就A,B,C这3个函数，最后把每一种的A * B * C加起来就好了
-
其实就是求组合，C(n,1),c(n,2),c(n,3)，跟动态规划没啥关系
#include <iostream> #include <vector> using namespace std; class project { void combin(vector<char> team, int pos, int n, vector<char>& item) { int size = team.size(); if (n == 0) { res.push_back(item); return; } for (int i = pos; i < size; i++) { item.push_back(team[i]); combin(team, i + 1, n - 1, item); item.pop_back(); } } public: vector<vector<char>> res; void getresult(vector<char> vecteam, int size) { vector<char> tmp; combin(vecteam, 0, size, tmp); } }; int main() { vector<char> team{ 'A','B','C' }; project p; p.getresult(team, 1); p.getresult(team, 2); p.getresult(team, 3); for (auto v : p.res) { for (auto c : v) { cout << c << " "; } cout << endl; } }
发表回复