uva 147 Dollars(完全背包)

点击打开链接uva 147

思路: 完全背包

分析:

1 很明显裸的完全背包，注意一个地方就是输入的值不一定是小数点只有2位，这边我们应该分成两部分输入，最后注意输出即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 30010;

long long dp[MAXN];
int v[12] = {0,10000,5000,2000,1000,500,200,100,50,20,10,5};

void solve(){
    memset(dp , 0 , sizeof(0));
    dp[0] = 1;
    for(int i = 1 ; i <= 11 ; i++)
        for(int j = v[i] ; j < MAXN ; j++)
            dp[j] += dp[j-v[i]];
}

int main(){
    solve();
    int x , y;
    while(scanf("%d.%d" , &x , &y) && x+y){
        int sum = x*100+y;
        printf("%3d.%02d%17lld\n" , x , y , dp[sum]);
    }
    return 0;
}