本文主要是介绍uva674(完全背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:
有5种硬币1,5,10,25,50,；现在随意的给出一个价钱，问你有几种组合方式！
输入11
输出4
1+...+1（10个），5+（6*1），5+5+1, 10+1（共4种）
思路；
满足完全背包思想，状态转移方程：dp[i+num[k]] += dp[i](dp[i]为组合成i的不重复种数，num[k]分别为1,5,10,25,50）不能合在一起转移，否则会导致重复！
代码：
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<cmath>
#include<string.h>
using namespace std;int coin[5]={1,5,10,25,50};
int dp[10000];
int main()
{int n;while(cin>>n){fill(dp,dp+n+1,0);dp[0]=1;for(int i=0;i<5;i++)for(int j=0;j<=n;j++)dp[j+coin[i]]+=dp[j];cout<<dp[n]<<endl;}}
这篇关于uva674(完全背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
