[BAEKJOON] 12865번 평범한 배낭

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

int main() {
	int N, K;

	std::cin >> N >> K;

	int * w		{ new int[N] };
	int * v		{ new int[N] };
	int *dp		{ new int[K + 1] };
	std::fill_n(dp, K + 1, 0);
	for (int i = 0; i < N; ++i) std::cin >> w[i] >> v[i];
	
	
	for (int i = 0; i < N; ++i) {
		for (int j = K; j >= 0; --j) {
			if (w[i] <= j) {
				dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	}
	std::cout << dp[K];

	delete[] w;
	delete[] v;
	delete[] dp;

	return 0;
}

 

풀 이

 

• N : 4 / W : 7
  6 13 | 4 8 | 3 6 | 5 12 

• 노란색의 경우 최대값 7에서 2번째 물건의 무게 3을 뺀 무게의 dp[4]의 값 8 과
  현재 2번째 물건의 가치 6을 더한 14가 이전의 있던 값보다 크다.
  if( w[i] <= j ) dp[j] = Max( dp[j] , dp[ j - w[i] ] + v[i]
  사용하지 않는 무게는 0이여야 하기 때문에 dp 배열을 0으로 초기화를 해줘야 한다. 

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/12865