POJ 1276 - Cash Machine


问题描述

有各种不同面值的货币,每种面值的货币有不同的数量,请找出利用这些货币可以凑成的最接近且小于等于给定的数字cash的金额。

解题思路

提示:动态规划,多重背包问题

第i种面额 d[i]n[i]+1 种选择方案,可以转化为01背包问题处理

转化的大概思路就是把 每种面值乘以其不同的个数,把得到的不同金额作为一件新的独一无二的货币,但是这样存在两个问题:

  • 一是 d[i]*ki 可能等于 d[j]*kj ,其中 ki ∈n[i],kj∈n[j]
  • 二是这样做一定TLE超时(前人经验,我就不重滔覆辙呐)

首先要解决存储问题,cash上限 10W 实在太大了,推荐用new,最后记得delete就是了,不然就算AC掉,Memory也会很大。

说到空间的申请,说点题外话,这题不像 [POJ1837](.//背包容量(最大可取金额)
N //物品种数(面额种数)
n[i] // 第i种物品的个数(第i种面额的数量)
d[i] // 第i种物品的价值(第i种面额的价值)


值得注意的是,如果设每个物品的价值为 `w[i]`,体积(可理解为消耗的价值)为 `c[i]`,那么必有 `d[i] = w[i] = c[i]` 。


如果把一个金额看为一种状态,那么一共有 `0~cash` 种状态。

显然其中可能会发生的 **状态范围为** `min{w[i] | 1<=i<=n[i]} ~ Cash`

那么可以建立一个状态数组 `dp[cash+1]`,

其中 `dp[j]` 记录的是 “最接近状态j,且`<=j`” 的状态值,即 `dp[j] <=j`

**J越接近 `dp[j]`,`dp[j]`的解越优,最理想是 `dp[j]=j`**

**需要注意的是,`dp[j]` 为了说明的是状态 j 可以发生,但不会理会 `dp[j]` 怎样发生**

例如有3张1元,1张3元,

那么我们既可以认为 `dp[3]=3` 是通过取3次1元得到,也可以认为 `dp[3]` 是通过取1次3元得到的,但无论怎样得到,`dp[3]=3` 都会发生。

**再需要注意的是,`dp[j]` 的状态值会累积**

再形象举例说明:例如有1张3元, `cash=4`

那么根据前面的说明,自然有 `dp[3]=dp[4]=3` ,就是说状态3、状态4都可以通过取1次3元发生,一旦发生,这个状态值3就会被保有在当前的状态 `dp[4]`,**这其实是起到一个优化作用,后面详细解释**

再接上例,当我们增加一个条件“有3张1元”,那么在已经被保存的前提 `dp[4]=3` 下,我们只需要通过取1次1元,就能得到比 `dp[4]=3` 的更优解 `dp[4]=4` ,但此时我们完全不用理会 `dp[4]=3` 是怎样来的,**我们只需要知道 `dp[4]=3` 一定会出现就足够了**


------


然后说说刚才提到的“**优化问题**”:

利用01背包的知识,不难理解 **状态方程** `dp[j]=dp[ j-c[i] ]+w[i]`

至于说方程是什么含义,看过01背包的大概也知道什么意思,没看的同学就别怪我不解释咯。

优化是因为状态值被记录了,就是说我们在取得下一个货币i之前,**当前的状态为** `j-c[i]`

一旦我们选取货币i,就会得到状态 `(j-c[i])+c[i]`,即状态j 。且状态j 的状态值 `dp[j]` 会加上 `w[i]`。 至于 `dp[j]` 原来值是多少,就无需理会,因为 `dp[j]` 的值是累积下来的,同样本次加上 `w[i]` 后,只要 `dp[j]` 值未到最优,它同样会成为下一次的累加值。

这样每次都直接调用前一次已获得的状态值,就可以节省一堆搜索的时间,这是DFS或BFS办不到的,也是动态规划的优点。


------


**接下来说说计数器count[j]**:

在我的程序中,**每更换一次面额,计数器会清零**,这样做是为了 以面额i的价值 `w[i]` 为权,根据选取该面额的个数,对状态值 `dp[j]` 进行 `w[i]` 的整数倍分割,这样就能得到对于每组状态 `dp[w[i]*k]` 到 `dp[w[i]*(k+1)] (0<=k<=n[i])` 之间,在当前面额 `w[i]` 下的最优状态值。

例如有 3张3元,

自然 `dp[0]=dp[1]=dp[2]=0`,`count[0]=count[1]=count[2]=0` 这是因为最小面额为3。

不难得到 `dp[3]=dp[4]=dp[5]=3`,`count[3]=count[4]=count[5]=1` 这是因为面额3元不可分,这3个状态的最优值就是取1次3元。

`dp[6]=dp[7]=dp[8]=6`,`count[6]=count[7]=count[8]=2` 这3个状态的最优值就是取2次3元。

`dp[9]=dp[10]=dp[11]=dp[…]=9`,`count[9]=count[10]=count[[11]=count[…]=3`  最多只有3张3元,以后的的状态的最优值均为9。


------


**最后说说用memset函数初始化的问题**:

程序中也说得很清楚了,由于是动态空间,不要用sizeof,要人为计算空间大小,记得+1

我认为这是memset函数的缺陷。。。(不敢叫BUG)


## AC 源码


```c
//Memory Time 
//1052K  47MS 

#include<iostream>
using namespace std;

int main(int i,int j)
{
    int N;   //物品种数(面额种数)    
    int cash;  //背包容量(最大可取金额)
    while(cin>>cash>>N)
    {
        /*Input*/

        int* n=new int[N+1];  //n[i]第i种物品的个数(第i种面额的数量)
        int* w=new int[N+1];  //w[i]第i种物品的价值(第i种面额的价值)
        int* c=new int[N+1];  //c[i]第i种物品的体积(第i种面额消耗的价值)
        int* dp=new int[cash+1];  //dp[j]记录的是 当前最接近状态j且<=j的值,dp值会累积
        int* count=new int[cash+1];//计数器,限制某种物品(面额)的选取个数

        for(i=1;i<=N;i++)
        {
            cin>>n[i]>>w[i];
            c[i]=w[i];    //本题的单个物品的“体积”等于其“价值”
        }

        /*Initial*/

        memset(dp,0,4*(cash+1));  //由于dp申请的是动态内存,用sizeof计算长度会出错
                                  //这里要用 类型大小*个数,这里为 int*(cash+1) , int大小为4

        /*DP*/

        for(i=1;i<=N;i++)
        {
            memset(count,0,4*(cash+1));  //每更换一次面额,计数器清零
            for(j=w[i];j<=cash;j++)      //对于第i种货币,其面额d[i]~cash间任一个状态都可能发生
                if(dp[j]<dp[j-c[i]]+w[i] && count[j-c[i]]<n[i]) //count[j-c[i]]<n[i]
                {                                               //取某种面额前,必须保证这次操作之前所取该种面额的次数小于n[i]
                    dp[j] = dp[j-c[i]]+w[i];    //选取第i个物品后,背包容量(允许取的最大金额)减少c[i]
                    count[j]=count[j-c[i]]+1;   //对于当前状态j,第i种面额被抽了count[j]次
                }
        }

        /*Output*/

        cout<<dp[cash]<<endl;

        /*Release Space*/

        delete n;
        delete w;
        delete c;
        delete dp;
        delete count;
    }

    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 2602 - Superlong sums POJ 2602 - Superlong sums
POJ 2602 - Superlong sums Time: 1000MS Memory: 65536K 难度: 初级 分类: 高精度算法 问题描述无。 解题思路非常恶心的大数相加 首先输入就够恶心了…哪有人逐位还要间断输入两个数的…
2011-09-16
下一篇 
POJ 1472 - Instant Complexity POJ 1472 - Instant Complexity
POJ 1472 - Instant Complexity Time: 1000MS Memory: 10000K 难度: 中级 分类: 模拟法 问题描述给出一段Pascial程序,计算其时间复杂度(能计算的项则计算,不能计算则化到最简
2011-09-14
  目录