[C++] 백준 4781번 사탕 가게

다이나믹 프로그래밍 문제입니다.

주어진 배낭에 최대한 많은 가치를 담는 문제와 동일한 문제입니다.
다른 점으로는 돈으로 실수(double)가 있는데 돈의 범위는 0.01 ~ 100.00 입니다.
이를 * 100해주어서 integer로 처리할 수 있도록 만들어주면 배낭문제와 동일해집니다.
이 때 double의 오차가 있을 수 있으므로 0.5를 더해주었습니다.

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

int n, c;
int DP[10010];
double m, p;
int mm, pp;
vector<pair<int, int> > v;

bool compare(const pair<int, int> &a, const pair<int, int> &b)
{
	if (a.second == b.second) {
		return a.first > b.first;
	}
	return a.second < b.second;
}

int main(int argc, char* argv[])
{
	while (1) {
		cin >> n >> m;
		
		mm = (int)(m * 100 + 0.5);

        v.clear();
		memset(DP, 0, sizeof(DP));

		if (n == 0 && mm == 0) {
			break;
		}

		for (int i = 0; i < n; ++i) {
			cin >> c >> p;

			pp = (int)(p * 100 + 0.5);

			v.push_back({ c, pp });
		}

		sort(v.begin(), v.end(), compare);

		for (int i = 0; i < v.size(); ++i) {
			DP[0] = 0;
			for (int j = 0; j <= mm; ++j) {
				if (j + v[i].second > mm) {
					break;
				}

				DP[j + v[i].second] = max(DP[j + v[i].second], DP[j] + v[i].first);
			}
		}

		cout << max(DP[mm], 0) << endl;
	}

	return 0;
}