[BOJ] 12865번 : 평범한 배낭

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, k; 
int w[100005], v[100005];
int d[100005]; // 무게에따른 최대 value값 저장 

int main(void) {
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cin >> n >> k; 
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; 

	for (int i = 1; i <= n; i++) {
		for (int m = k; m >= w[i]; m--) {
			d[m] = max(d[m], d[m - w[i]] + v[i]); 
		}
	}
	cout << *max_element(d, d + k + 1) << '\n';
}

1. 무게에 따른 최대 value값을 저장하는 table을 정의한다.

2. 점화식을 정의한다. d [w] = max(d [w], d [w-weight [i]] + value [i])로 구한다. ( 이때, for loop에서 역순으로 시행하는 이유는 정방향으로 시행했을 때는, 중복으로 더해지는 문제가 발생한다.)  

3. 초기값을 설정한다. 여기서는 다 0으로 초기화하면 된다.