c++_백준_12865_"평범한 배낭"

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

12865번: 평범한 배낭

 

​

범위가 넓어 DP를 이용하여 해결하였다.

​

역시 DP는 골드 5라도 나에게

난이도가 너무 높다.

 

물품의 수를 i,

무게를 j

라고 두어

​

0~i (N) 개,

0~ j (K)무게

로 지정했다.

​

​

코드를 보면 알겠지만

주로 봐야할 부분은

weight[i] <= j 일 때이다.

​

예를 들어

j = 7,

weight[i] = 5 라면

즉, 한 물품의 무게가 5 라면

DP[i-1][j - weight[i]] + value[i] 의 의미는

무게가 (7 -5) 2일 때 최고의 가치 + i 의 현재 가치(현재 행의 가치)

와

DP[i-1][j] : 이전 검사했던 j 무게 중 가장 높은 가치

중 가치가 높은 것을

DP[i][j] 넣었다.

 

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

int N, K;

int weight[101];
int value[101];

int DP[101][100001];

void find_total() {

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (weight[i] <= j)
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - weight[i]] + value[i]);
			else
				DP[i][j] = DP[i - 1][j];
		}
	}
	
	cout << DP[N][K];
}

int main(void) {

	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		cin >> weight[i] >> value[i];
	}

	find_total();

}

​