杭电ACM——2069，Coin Change（DP）-白红宇

杭电ACM——2069，Coin Change（DP）

阅读量：4049 次

发布时间：2019-05-25

本文共 811 字，大约阅读时间需要 2 分钟。

看了这位大佬的博客：

发现，原来这是一道二维费用的背包问题。

设置三维数组dp[i,j,k]：

状态：dp[i,j,k]表示用前i种硬币，硬币用了j个，总面值为k的最大方案数

状态转移方程：

dp[i,j,k]=

{

dp[i-1,j,k] , k<a[i]

dp[i-1,j,k]+dp[i,j-1,k-a[i]], k>=a[i]

}

大佬是用二维滚动数组来完成的，则

dp[j,k]=dp[j,k]+dp[j-1,k[a[i]]

代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int dp[101][251],a[6]={0,1,5,10,25,50}; int main(){    int n,i,j,k,T,ans;    while(cin>>n)    {            memset(dp,0,sizeof(dp));        dp[0][0]=1;ans=0;        T=1;        if(n>=50) T=5;        else if(n>=25) T=4;        else if(n>=10) T=3;        else if(n>=5) T=2;        for(i=1;i<=T;i++)            for(j=1;j<=100;j++)                for(k=a[i];k<=n;k++)                    dp[j][k]+=dp[j-1][k-a[i]];        for(i=0;i<=100;i++)            ans+=dp[i][n];        cout<
       
        <