算法与acm

poj1276 Cash Machine 状态dp

2008年11月19日 阅读(432)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
ok,这道题,的意思是给你一堆钱,各种面值的都有,比如10块的5张,5块的3张,2块的1张,请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额,比如cash=33块。
我们可以取3张10块+2张1块=32,就是我们可以找到的那个最接近且小于33的数额。

面额保存在D[n]数组里,相应的张数保存在N[n]数组里,考虑这个题目,实际上可以正向dp,也就是我们在及时加上面额D[i]时组成的钱的可能数额,可以利用前面D[0] …..D[i-1]的结果,这样我们只要保存下这些前面的可能组成的数额,比如我们用一个100001的bool数组元素sign[1000001],sign[i]保存能否组成该数额i。

然后最简单的是利用一个3重循环,但这样会tle
void solve_1(int D[20],int N[20],int cash,int n){
  bool sign[2][MAX_N];
  memset(sign,false,sizeof(sign[0])*2);
  sign[0][0] = true;
  int i;
  for(i = 0 ; i < n ; i++){
    for(int j = 0 ; j <= N[i] ; j++){
        int temp = D[i]*j;
        for(int k = 0 ; k+ temp <= cash ; k++){
                if(sign[i%2][k])
                     sign[(i+1)%2][k+temp] = true;   
        }
    }
  }
  int j;
  for(j = cash ; j >= 0 ; j–){
    if(sign[i%2][j]) break;
  }
  printf("%d\n",j);

}
实际上直接从0…..i得到0……i+1,i就代表了第i种面额,
比如可以利用前i项组合出x元,这样我们再利用循环,x+D[i+1]*j也是可以组合出来的
所以只需要枚举x和j就可以了。总的复杂度是n*max{N[i]}*100000

需要继续优化,
我们修改内层循环的先后顺序,我们首先从高到低枚举现在已经可以得到的现金额,从这个额度开始,让它不断扩充当前的一个新的可用面值D[i+1]。
比如我们已经得到现在可以得到的金额有
1 3 8 10 15,第i+1个面值为2,该面值纸币数目为3
这样我们从15开始,则可以得到15 17 19 21
从10开始,则可以得到10 12 14 16
从8开始,则可以得到8 10 12 14
看到了吧,优化的空间在这里,我们从8又来到了10,实际上我们发现10已经形成了就不用再往下进行了,优化的空间就在这里了。为了优化我们还需要额外记住形成当前面值所需要的D[i+1]的数额,如果我们后来又到了一个已经形成的面值,比较当前用掉的D[i+1]的个数,和以前的那个个数,如果大于以前的个数,显然不用继续进行了。

Problem: 1276
User: phylips Memory: 804K
Time: 0MS Language: G++
Result: Accepted

  • Source Code
  • #include <cstdio>

    #include <cstring>

    #include <cstdlib>

    #define MAX_N 100001

    #define MAX_INT 1000000

    #define debug

    #undef debug

    using namespace std;

    void solve(int D[20],int N[20],int cash,int n){

    bool sign[MAX_N];

    int sign_num[MAX_N];

    memset(sign,false,sizeof(sign));

    sign[0] = true;

    int i;

    for(i = 0 ; i < n ; i++){

    memset(sign_num,MAX_INT,sizeof(sign_num));

    for(int k = cash ; k >= 0 ; k–){

    if(sign[k])

    for(int j = 0 ; k+ D[i]*j <= cash && j <= N[i]; j++){

    if(sign[k+D[i]*j] && j >= sign_num[k+D[i]*j]){

    #ifdef debug

    //printf("test:%d j:%d %d\n",k+D[i]*j,j,sign_num[k+D[i]*j]);

    #endif

    break;

    }

    else{

    sign[k+D[i]*j] = true;

    sign_num[k+D[i]*j] = j;

    }

    }

    }

    #ifdef debug

    for(int t = 0 ; t < cash ; t++){

    if(sign[t])printf("%d ",t);

    }

    printf("\n");

    #endif

    }

    int j;

    for(j = cash ; j >= 0 ; j–){

    if(sign[j]) break;

    }

    printf("%d\n",j);

    }

    int main()

    {

    int cash,n;

    int D[20],N[20];

    while(scanf("%d%d",&cash,&n) == 2 ){

    if(n==0)

    {

    printf("0\n");

    continue;

    }

    for(int i = 0 ; i < n ; i++){

    scanf("%d%d",&N[i],&D[i]);

    }

    solve(D,N,cash,n);

    }

    return 0;

    }

You Might Also Like