[백준] boj12865

1. 풀이 방식( DP, 재귀, 반복문)

- 재귀 풀이 방식(search) : 첫번째 아이템부터 하나씩 선택해나가면 최대값을 찾음

                        메모제이션을 활용하여 이미 찾은 값은 또 찾지 않도록 처리

- 반복문 방식 (search2) : 가능한 모든 무게에 item을 하나씩 추가 하여 가장 큰 가중치를 찾아나감

 

2. 유의 사항 : 없음

출처: https://survivalking.tistory.com/75 [생존몬의 프로그래밍 블로그]

 

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAX 100000

int N, K;
int W[101];
int V[101];
int dp[101][MAX + 1];
int dp2[MAX + 1];

int search(int pos, int w) {
	if (w > K) return -987654321;
	else if (pos == N || w == K) return 0;

	int& ret = dp[pos][w];

	if (ret != -1) return ret;

	ret = 0;

	ret = max(search(pos + 1, w + W[pos]) + V[pos], search(pos + 1, w));

	return ret;
}

int search2() {

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= K; ++j) {
			if (j + W[i] > K) continue;
			dp2[j] = max(dp2[j], dp2[j + W[i]] + V[i]);
		}
		for (int k = 0; k <= K; ++k)
			cout << k << " " << dp2[k] << endl;
		cout << "---" << endl;
	}

	return dp2[0];
}


int main() {
	.//freopen("test.txt", "r", stdin);

	cin >> N >> K;

	for (int i = 0; i < N; ++i) {
		cin >> W[i] >> V[i];
	}

	for (int i = 0; i < 101; ++i) {
		memset(dp[i], -1, sizeof(int) * (MAX + 1));
	}


	//cout << search(0, 0) << endl;

	cout << search2() << endl;

	return 0;
}