[4781] 사탕 가게

https://www.acmicpc.net/problem/4781

4781번: 사탕 가게

<문제>

간단한 냅색문제, 실수로 들어오는게 특징이라면 특징인데, 100을 곱해서 정수로 처리했다.

100*m <= 10000이기에 배열의 크기를 1만개로 잡아주고, 실수오차를 방지하기 위해 int변환 전에 +0.5를 해주었다.

사탕의 개수가 무한하므로 정방향으로 dp를 채워주면 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int w[10001], v[10001], dp[10001];
int main(void) {
    int n, m;
    double _m;
    while (1) {
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        memset(dp, 0, sizeof(dp));
        cin >> n >> _m;
        if (n == 0) break;
        m = (int)((_m * (double)100) + 0.5);
        int i, j;
        for (i = 0; i < n; i++) {
            int c;
            double p;
            cin >> c >> p;
            v[i] = c;
            w[i] = (int)((p * (double)100) + 0.5);
        }
        for (i = 0; i < n; i++)
            for (j = w[i]; j <= m; j++) dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
        cout << dp[m] << '\n';
    }
    return 0;
}