本文主要是介绍【背包问题】1分2分5分的硬币，组成1角，共有多少种组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
设1分个数为x，2分个数为y，5分的硬币个数为z，则1*x+2*y+5*z=10；5*z=10-x-2*y；即：
z x对应可能的取值
0 10 8 6 4 2 0（6个）
1 5 3 1（3个）
2 0（1个）
总共个数为6+3+1=10.
因此，按照规律，本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数
某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以，求总的组合次数可以编程为：
number=0;
for (int m=0;m<=10;m+=5)
{
number+=(m+2)/2;
}
cout<<number<<endl;这样程序是不是简单多了（只需要累加3次，而上面的3层循环呢？大家自己想想）。别人考你肯定不是考你会不会编这个程序，是考你如何去使程序的复杂度降低。
6分、4分、2分组成100分怎么处理？
2分为x，4分为y，6分为z。则6*z=100-2*x-4*y，可化简为：
3*z=50-x-2*y
z可能的取值为0、1、2···16，
当z=0时，x可以为50 48 46···2 0（26个）
当z=1时，x可以为47 45 43···3 1（24个）
当z=2时，x可以为44 42 40···2 0（23个）
当z=3时，x可以为41 39 37···3 1（21个）
·
·
·
当z=15时，x可以为5 3 1（3个）
当z=16时，x可以为2 0（2个）
因此，按照规律，本题目组合总数为50以内的偶数+47以内的奇数+44以内的偶数+···+5以内的奇数+2以内的偶数
某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以，求总的组合次数可以编程为：
number=0;
for (int m=0;m<=50;m+=3)
{
number+=(m+2)/2;
}
cout<<number<<endl;是不是可以看出规律了呢？实际上就是看表达式（这里是3*z=50-x-2*y），就是把最大乘数（这里是3）放在一边，这也是m增加的步长。而m的最大取值也就是表达式中的这个常数。
当然这也是个典型的背包问题：
int dp[10+1];int main()
{int w[] = {1,2,5};dp[0] = 1;for(int i=0; i<3; i++){for(int j=w[i]; j<=10; j++){dp[j] += dp[j - w[i]];}}printf("%d\n",dp[10]);return 0;
}这篇关于【背包问题】1分2分5分的硬币，组成1角，共有多少种组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
