[백준] 12865번 - 평범한 배낭 (파이썬, C++)

문제) 백준 - 동적 계획법 (Dynamic Programming) - 평범한 배낭

-> www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

	1	2	3	4	5	6	7
( 6, 13 )	0	0	0	0	0	13	13
( 4, 8 )	0	0	0	8	8	13	13
( 3, 6 )	0	0	6	8	8	13	14
( 5, 12 )	0	0	0	0	12	13	14

 

(물건 무게, 가치)가 (3, 4)인 경우를 주목하자.

1. 가방의 무게를 1부터 7까지 늘려가며 (3, 4)를 넣어준다.

2. 1과 2는 물건 무게보다 작으므로 이전 무게를 채택한다.

3. 3부터 7까지는 물건을 넣은 뒤 남은 무게로 채울 수 있는 값과 이전 최댓값을 위의 행에서 가져온다.

4. 둘의 최대를 비교한다.

 

점화식 : dp[ i ][ j ] = max( dp[ i - 1][ j ], dp[ i - 1 ][ j - weight_value[ i ][ 0 ] ] + weight_value[ i ][ 1 ])

 

 

Python 소스 코드)

 

	import sys
	input = sys.stdin.readline
	n, k = map(int, input().split())
	#인덱스를 1부터 사용하기 위한 처리
	weight_value = [(0, 0)]
	for i in range(n):
	w, v = map(int, input().split())
	weight_value.append((w, v))
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
	for j in range(1, k + 1):
	if j >= weight_value[i][0]:
	dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_value[i][0]] + weight_value[i][1])
	else:
	#물건 무게가 현재 무게를 초과하면 이전 값을 채택
	dp[i][j] = dp[i - 1][j]
	print(dp[n][k])

view raw 12865.py hosted with ❤ by GitHub

 

2021/6/8 Update

---

 

C++소스 코드)

 

	#define _CRT_SECURE_NO_WARNINGS
	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 101
	#define MOD 10007
	using namespace std;
	typedef pair<int, int> p;
	int n, k, cache[101][100001];
	p items[101]; //무게, 가치
	int solve(int capacity, int item) {
	//기저사례: n개의 item을 확인하면 fin
	if (item == n) return 0;
	int& ret = cache[item][capacity];
	if (ret != -1) return ret;
	//물건을 담지 않을 경우
	ret = solve(capacity, item + 1);
	//물건을 담을 경우
	if (capacity >= items[item].first)
	ret = max(ret, solve(capacity - items[item].first, item + 1) + items[item].second);
	return ret;
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	cin >> items[i].first >> items[i].second;
	memset(cache, -1, sizeof(cache));
	cout << solve(k, 0) << endl;
	return 0;
	}

view raw 12865.cpp hosted with ❤ by GitHub

각 물건에 대해 물건을 넣을지, 안넣을지에 대한 경우의 수에서 물건들의 가치의 합을 계산한다. 완전탐색으로 구현할 경우, 시간복잡도는 O(2^n)이므로 시간 제한에 걸린다. 따라서 memoization을 통해 가방에 용량이 capacity만큼 남았을 때, item 이후 물건들을 넣어 얻을 수 있는 가치의 최대를 구한다.

 

 

ps. 2차원 배열보다 이해가 훨씬 쉬운듯하다...킹만북