[BOJ/Gold 4] 백준 33535 Impressive Beers(C++)

문제 링크

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

 

문제

You and your friends find yourselves in a bar after class. As you are a really big fan of specialty beers you want to drink as many different beers as possible. Only issue of course being that you are still a student, and therefore you do not have enough money to buy every beer in the pub.

But of course, all beers are not created equally! You know of every type of beer the price and how much happiness it will give you. As you want to be as happy as possible, and being a Delft student, you want to find out how much happiness you can buy using an optimal strategy. So you decide to write a program that tells you how much happiness you can buy with a given amount of money. But since you like to drink different beers, you will never order the same beer twice, your program should take this into account.

 

입력

One line with two integers: N,1 ≤ N ≤ 500 the number of different beers the pub offers, and M,1 ≤ M ≤ 10,000, the amount of money that you have.

Followed by N lines with on each line a type of beer which is indicated by two integers: p,1 ≤ p ≤ 1,000, the price of the beer and h,1 ≤ h ≤ 1,000, the happiness you will gain from this beer.

 

출력

A single line with a single integer H, the maximal happiness you can gain by buying different kinds of beers, within your budget.

 

예제 입력 1

5 20
20 50
10 30
5 15
4 12
9 20

예제 출력 1

57

In the first sample your max happiness will be 57, as you can buy the beers priced 10, 5 and 4 to come to a hapiness of 57 (with a singe coin left to spend, buy there is no more beer you could buy for this price). Every other combination will give you less hapiness or will cost more than your budget. (for example, the beers of 10 + 9 will give you only 50 hapiness).

예제 입력 2

5 100
20 50
10 30
5 15
4 12
9 20

예제 출력 2

127

 

In the second sample you will buy each beer, giving you 127 hapiness, but it will not give you any more satisfaction to buy the same beer multiple times, so you are stuck at 127 and have some money left.

 

알고리즘 분류

• 배낭 문제

 

풀이

아

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 501
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int P[MAX], H[MAX];
int DP[MAX][10001];
int Answer;

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> P[i] >> H[i];
	}
}

void settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = M; j >= 0; j--) {
			if (j - P[i] >= 0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - P[i]] + H[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}
	for (int i = 0; i <= M; i++) {
		Answer = max(Answer, DP[N][i]);
	}
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO

	input();
	settings();
	printAnswer();

	return 0;
}