백준 Gold 4 사탕 가게

사탕 가게 (백준 Gold 4)

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

사탕의 종류 N과 돈의 양 M이 주어진다
사탕의 칼로리와 가격이 주어질 때
M으로 만들 수 있는 가장 높은 칼로리를 구하기

풀이 방법

기본적인 배낭 문제 타입의 DP 문제
다만, M이 소수점으로 주어지기에 캐스팅을 잘 해야한다

*100 + 0.5를 통해 int 캐스트하여 다른
0/1 배낭 문제처럼 풀 수 있다

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	while (true)
	{
		int n;
		double m;
		cin >> n >> m;

		if (n == 0)
			break;

		vector<int> weights;
		vector<int> vals;

		for (int i = 0; i < n; i++)
		{
			int t;
			double w;
			cin >> t >> w;
			vals.push_back(t);
			weights.push_back(w * 100 + 0.5);
		}

		int mv = m * 100 + 0.5;

		vector<int> dp(mv + 1);

		for (int i = 0; i < n; i++)
		{
			for (int j = weights[i]; j <= mv; j++)
			{
				dp[j] = max(dp[j], dp[j - weights[i]] + vals[i]);
			}
		}

		cout << dp[mv] << '\n';
	}

	return 0;
}

결과

여담으로
*100 + 0.5를 해주는 이유는
‘일반적인’ 부동 소수점 표기에 따라서
29.0 -> 28.9…. 이런 식으로
실제 내부에 표기될 가능성이 존재하며
해당 부동 소수점 값이 커질 수록, 이러한 사소한 오차가 발생 가능하다
(그렇기에 원본보다 아주 살짝 작은 값이 저장)

• 그렇기에 0.5를 더하여
  아주 살짝 작은 값을 원본보다 크게 만들되
  int 캐스트 될때, 반올림되지는 않게 값을 보정 하는 것