注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

祝灾区人民早日度过难关

努力工作

 
 
 

日志

 
 

又是一个深夜  

2007-04-12 04:02:19|  分类: 真我风采 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    一道简单的DP题,花去了我3个多小时的时间,同时付出大量时间的是skatou和小胖。在这里不得不感谢skatou和小胖,尤其是小胖,面对我这个番薯脑子,一遍又一遍地帮我解释,实在是感激涕零。
    题目如下 :
    Cash Machine
Time limit: 10 Seconds   Memory limit: 32768K  
Total Submit: 1767   Accepted Submit: 640  

A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,

N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10

means the machine has a supply of 10 bills of 100 each, 4 bills of 50 each, and 5 bills of 10 each.

Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine. The program input is from a text file. Each data set in the file stands for a particular transaction and has the format:

cash N n1 D1 n2 D2 ... nN DN

where 0 <= cash <= 100000 is the amount of cash requested, 0 <= N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k = 1, N. White spaces can occur freely between the numbers in the input. The input data are correct. For each set of data the program prints the result to the standard output on a separate line as shown in the examples below.
Sample Input     Sample Output     Comment
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10     735
630
0
0     735=1* 350+3* 125+2* 5
630=6* 100+1* 30 or 21* 30
No cash delivered
No cash delivered

The first data set designates a transaction where the amount of cash requested is 735. The machine contains 3 bill denominations: 4 bills of 125, 6 bills of 5, and 3 bills of 350. The machine can deliver the exact amount of requested cash.

In the second case the bill supply of the machine does not fit the exact amount of cash requested. The maximum cash that can be delivered is 630. Notice that there can be several possibilities to combine the bills in the machine for matching the delivered cash.

In the third case the machine is empty and no cash is delivered. In the fourth case the amount of cash requested is 0 and, therefore, the machine delivers no cash.
Problem Source: Southeast Europe 2002

给定N种一定数目的纸币(如2张100,3张50),对于给定的货币数量上限(如239),求出能凑出的最大数额(要小于239,这里是2×100=200)
和找零钱问题类似,但是又不太一样。
我的方法很土,开一个很大的数组,把所有可以找出的数额算出来,从0开始往后算,如果能组成数额为i的总额,把a[i]置1。这个方法不土,土的是,我想把每次计算时用掉的货币数目记录下来。这要耗去大量内存,并且减慢速度。
我的思维还是转不过弯来,停留在枚举阶段。
我的满脑子里想的是,有n张货币,要枚举2^n种情况。记录用掉的货币数目,就是残余的枚举思想在作怪。
DP意味着,大量重复的状态被合并了,只记录合并后的状态。
在这里,重复的状态是什么呢?就是用不同的货币,组成相同的总额。也就是说,用掉的货币数目不一样无所谓,对我们来说,只有总额是有用的信息。这样就大大减少了计算量。
DP意味着,兴趣不再放在所有的情况,而是放在某一状态上,这一状态合并了大量的情况。
对DP来说,计算的顺序很重要。
思路就明朗了,对每张货币,对整个数组进行扫描。一看到1,表示a[k]的下标表示的总额k是有效的,再加一张货币D[i],把数组对应元素a[k+D[i]]再置1,就OK啦

    memset(a,0,sizeof(int)*(cash+1));
    a[0]=1;
    for(int i= 0;i<N;i++)
        for(int j = 0;j < ncash[i];j++)
        for(int k = 0;k<= cash;k++)
            if(a[k]&&k+D[i]<=cash)
                a[k+D[i]] = 1;
    for(int i = cash;i>=0;i--)
        if(a[i])
            return i;

sample过了,边界测试,总额100000,1000张1000元货币,已经有点慢了,不安地提交,华丽地TLE。
百思不解,幸得小胖点拨,1000张1000元货币是一样的,我却把他们当成不一样的来处理,每张货币都要扫描一下数组,太浪费时间啦。复杂度是O(N*L),N是总额,100000,L是货币张数,最多为10000,所以就很慢了。
我改进了一下,变成同一面值的货币扫描一次。代码如下:
    memset(a,0,sizeof(int)*(cash+1));
    a[0]=1;
    memset(scan,0,sizeof(int)*(cash+1));
    for(int i= 0;i<N;i++)
    {
        int ns=0;
        for(int k = 0;k<= cash;k++)
            if(a[k])
                scan[ns++]=k;
        for(int k = 0;k < ns;k++)
            for(int j = 0;j<ncash[i];j++)
                if(scan[k]+(j+1)*D[i]<=cash)
                    a[scan[k]+(j+1)*D[i]] = 1;
        memset(scan,0,sizeof(int)*ns);
    }
    for(int i = cash;i>=0;i--)
        if(a[i])
            return i;
这样复杂度降低为O(N*n)其中n为货币种类,最多为10,速度提高了千倍。
立马AC。
总结:
DP的思维很重要,他和枚举思维的区别在于:
善于发现状态,找出状态之间的递推关系。
抛弃不必要的信息,记录这些信息只会把单一状态变成多种情况,退化到枚举思维。
注意计算顺序。
计算一些看起来不必要的信息,表面上降低速度,实际上大大提高了速度,因为它记录了中间结果,避免重复计算。
  评论这张
 
阅读(126)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018