Coin Change UVA - 674 背包

本文主要是介绍Coin Change UVA - 674 背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

从小的到大枚举面额（这个必须在外面循环）

比如 枚举 dp[0] = 1,dp[1] = 1,dp[2] = 1,d[3] = 1,dp[4] = 1

当枚举到dp[5]的 时候 第一遍 的结果是 dp[5] += dp[5-1] 此时 dp[5] = dp[4] = 1（实际上dp[5] = 2），下一个循环枚举到

dp[5]的时候，dp[5] += dp[5-5] = 2。这样单独看某个值，最后都会遍历到每一个面值，也就是最终会满足dp方程

这样 第一遍 dp[6] += dp[6-1] =>dp[6] = dp[5] = 1, 第二遍 dp[6] += dp[6-5] =>dp[6] = 1 + dp[1] 不会重复。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=11000;
int dp[N],b[10]={1,5,10,25,50};
int main()
{int n,i,j;//printf("%d\n",p[17]);dp[0]=1;for(i=0;i<5;i++){for(j=b[i];j<N;j++){dp[j]+=dp[j-b[i]];}}while(~scanf("%d",&n)&&n){printf("%d\n",dp[n]);}return 0;
}

这篇关于Coin Change UVA - 674 背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---