UVA 147 Dollars (완전 가방)

UVA 147 Dollars (완전 가방)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83
제목:
       액면가 가 $100, $50, $20, $10, $5, $2, $1, 50c, 20c, 10c, 5c 의 11 가지 동전 이 있 습 니 다. 각 동전 은 무한 사용 할 수 있 습 니 다. 지금 은 임의의 금액 x (x < = 300.00 $) 를 드 리 겠 습 니 다. 위의 11 가지 동전 으로 x $를 구성 할 수 있 는 방법 이 몇 가지 가 있 습 니까?
분석:
       모든 동전 의 수량 이 무한 하기 때문에 본 문 제 는 완전한 가방 문제 로 볼 수 있다.
       우선 우 리 는 더 블 달러 를 정수 센트 로 바 꿔 야 한다. 다음 과 같은 두 가지 방법 이 있다.
       1.    double * 100 을 int 센트 로 직접 바 꾸 면 됩 니 다. 단, + 0.5 수 진 치 를 필요 로 합 니 다.
       2.    scanf ("% d.% d", & m1, & m2) 로 읽 습 니 다.
       다음은 가방 을 완전히 처리 하 는 과정 입 니 다.
       우 리 는 val [i] 에 게 제 i 종 동전 의 액면 가 를 표시 하고 dp [i] [j] = x 는 전 i 종 동전 으로 액면가 j 센트 를 구성 하 는 데 x 가지 방식 이 있다 는 것 을 나타 낸다.
       초기 값 dp 는 0 이 고 dp [0] [0] = 1. 상태 방정식 은:
       dp[i][j] = sum( dp[i-1][j] , dp[i][j-val[i]] ) //sum 은 화 해 를 추구 합 니 다.
       결국 우리 가 원 하 는 것 은 dp [n] [x] 의 값 이다.
       어떻게 상술 한 상태 전이 방정식 을 이해 합 니까?
       먼저 dp [i] [j] 를 살 펴 보면 앞 i 의 동전 으로 j 센트 를 구성 하 는 방법 수 를 나타 낸다. 그러면:
       1.    만약 우리 가 i 종 동전 (전 i - 1 종 동전 만 사용 하면 된다) 을 전혀 사용 하지 않 는 다 면, 우 리 는 dp [i - 1] [j] 방식 으로 j 센트 를 구성 할 수 있다 는 것 을 알 수 있다.
       2.    만약 우리 가 적어도 1 개의 i 번 째 동전 으로 j 센트 를 구성한다 면, 우 리 는 dp [i] [j - val [i]] 방법 이 목적 을 달성 할 수 있다 는 것 을 알 수 있다.
       다시 말 하면 dp [i] [j] = = 전 i 종의 동전 으로 j 센트 를 구성 하 는 방법 총수 = sum (dp [i - 1] [j], dp [i] [j - val [i]]).
프로그램 이 사용 하 는 스크롤 배열 이 므 로 dp 는 [j] 이 차원 만 있 습 니 다. 또한 j 는 어 릴 때 부터 큰 순환 을 해 야 합 니 다. (왜 그런 지 생각해 보 세 요)
AC 코드:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=30000+5;

int n=11;//    
int val[]={5,10,20,50,100,200,500,1000,2000,5000,10000};
long long dp[maxn];

int main()
{
    //   
    memset(dp,0,sizeof(dp));
    dp[0]=1;

    //    
    for(int i=0;i<n;i++)
        for(int j=val[i];j<maxn;j++)
            dp[j] += dp[j-val[i]];

    //    
    double money;
    while(scanf("%lf",&money)==1 && money>0)
    {
        //double       ,  +0.5
        //   scanf("%d.%d",&m1,&m2);    money
        int m=(int)(money*100+0.5);
        printf("%6.2lf%17lld
",money,dp[m]);
    }

    return 0;
}