小P的故事——神奇的换零钱(递推式完全背包)

浅浅的花香味﹌ 2022-07-12 08:15 126阅读 0赞

think:  
1上午比赛自己一直卡在了这个题目上，自己一直在用递推的方法找递推方程，下午补题问身边同学是要用递推式完全背包来做，因为递推的子问题是有序的，而这个题目其子问题是无序的，而且符合一种最优子结构  
2题目需要特别注意的是提示了输入数据超过了32000组，如果按照每个输入数据都开始按照动态转移方程重新计算更新的话会超时，因此建议开始输入前将所有可能数据的情况统一计算，之后直接输出对应的数据就行  
3自己还有不明白的地方就是为什么这个题目要把dp\[0\] = 1， 但是如果不是把dp\[0\] = 1的话，按照dp\[1\] = 1, dp\[2\] = 2, dp\[3\] = 3的话就会有数据重复计算，自己用代码尝试了一下，发现后台并没有评判n = 0的情况，呃，这里是自己错了，题目提示说了N是正整数，引以为戒，以后审题一定要细心

小P的故事——神奇的换零钱  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
已知A国经济很落后，他们只有1、2、3元三种面值的硬币，有一天小P要去A国旅行，想换一些零钱，小P很想知道将钱N兑换成硬币有很多种兑法，但是可惜的是他的数学竟然是体育老师教的，所以他不会啊、、、他只好求助于你，你可以帮他解决吗？  
提示：输入数据大于32000组。

Input  
每行只有一个正整数N，N小于32768。

Output  
对应每个输入，输出兑换方法数。

Example Input  
100  
1500

Example Output

884  
188251

Hint

Author  
xfl

以下为accepted代码——dp\[0\] = 1, n = 0输出1

#include <stdio.h>
    #include <string.h>
    int main()
    {
        int n, i, j, c[] = {1, 2, 3};
        int dp[40000];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(i = 0; i < 3; i++)
        {
        
            for(j = c[i]; j <= 32768; j++)
            {
        
                dp[j] = dp[j] + dp[j-c[i]];
            }
        }
        while(scanf("%d", &n) != EOF)
        {
        
            printf("%d\n", dp[n]);
        }
        return 0;
    }
    /* 判断为递推式完全背包的依据：递推通常表现为子问题有序性，即子问题内顺序不同即可认为方案不同，例如上台阶问题中先上一节台阶再上两节台阶和先上两节台阶再上一节台阶属于不同方案，而在本题目，把3元钱先换给1元钱再换给2元钱，与把三元钱先换给2元钱再换给1元钱属于同一方案*/
    
    
    
    
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 16ms
    Take Memory: 256KB
    Submit time: 2017-02-18 15:29:38
    ****************************************************/

以下为accepted代码——n = 0输出0

#include <stdio.h>
    #include <string.h>
    int main()
    {
        int n, i, j, c[] = {1, 2, 3};
        int dp[40000];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(i = 0; i < 3; i++)
        {
        
            for(j = c[i]; j <= 32768; j++)
            {
        
                dp[j] = dp[j] + dp[j-c[i]];
            }
        }
        while(scanf("%d", &n) != EOF)
        {
        
            if(n != 0)
                printf("%d\n", dp[n]);
            else
                printf("0\n");
        }
        return 0;
    }
    /* 判断为递推式完全背包的依据：递推通常表现为子问题有序性，即子问题内顺序不同即可认为方案不同，例如上台阶问题中先上一节台阶再上两节台阶和先上两节台阶再上一节台阶属于不同方案，而在本题目，把3元钱先换给1元钱再换给2元钱，与把三元钱先换给2元钱再换给1元钱属于同一方案*/
    
    
    
    
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 16ms
    Take Memory: 260KB
    Submit time: 2017-02-18 15:38:12
    ****************************************************/

以下为time limit exceeded——重复计算

#include <stdio.h>
    #include <string.h>
    int main()
    {
        int n, i, j, c[] = {1, 2, 3};
        int dp[40000];
        /*memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(i = 0; i < 3; i++)
        {
        
            for(j = c[i]; j <= 32768; j++)
            {
        
                dp[j] = dp[j] + dp[j-c[i]];
            }
        }*/
        while(scanf("%d", &n) != EOF)
        {
        
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for(i = 0; i < 3; i++)
            {
        
                for(j = c[i]; j <= n; j++)
                {
        
                    dp[j] = dp[j] + dp[j-c[i]];
                }
            }
            printf("%d\n", dp[n]);
        }
        return 0;
    }
    /* 判断为递推式完全背包的依据：递推通常表现为子问题有序性，即子问题内顺序不同即可认为方案不同，例如上台阶问题中先上一节台阶再上两节台阶和先上两节台阶再上一节台阶属于不同方案，而在本题目，把3元钱先换给1元钱再换给2元钱，与把三元钱先换给2元钱再换给1元钱属于同一方案*/
    
    
    
    
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-02-18 15:28:59
    ****************************************************/