백준 12865. 평범한 배낭
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
대표적인 냅색 문제라고 한다.
물건의수(n) x 최대무게(k) 의 배열을 만든다.
물건의수 n = 4, 최대무게(k) = 7
무게, 가치
6 13
4 8
3 6
5 12
dp[i][j] = max( dp[i-1][j-w[i]] + item[i], d[i-1][j] )
해당 차례의 물건을 담을수 있을때,
1. 해당 차례 물건 담음. dp[i-1][j-w[i]] + item[i]
2. 해당 차례 물건 담지 않음. dp[i-1][j]
1번 물건은 무게 6, 가치 13
무게 0일때 0
무게 1일때 0 (못넣음)
무게 2일때 0
무게 3일때 0
무게 4일때 0
무게 5일때 0
무게 6일때 13 (1번 물건 넣음)
무게 7일때 13
2번 물건은 무게 4, 가치 8
무게 0일때 0
무게 1일때 0
무게 2일때 0
무게 3일때 0
무게 4일때 8 (2번 물건 넣음)
무게 5일때 8 // 2번 물건 넣음 = 8, 2번 물건 안넣으면 전번 물건 담았을때 배낭 무게 최대값(dp[i-1][j]) = 0
// 2번물건 넣음: ( 2번 물건 넣음 = 8 )+ ( 현재무게6 - 2번물건무게4 = 2 따라서 dp[i-1][2] = 0) = 8
// 2번물건 안넣음: dp[i-1][j] = 13
// max(8, 13) = 13
무게 6일때 13
...
#include <iostream>
using namespace std;
#include <algorithm>
int dp[101][100001] = {0};
int item[101];
int w[101];
int main() {
int n;
cin >> n;
int k;
cin >> k;
for(int i = 1; i <= n; i++) {
scanf("%d %d", &w[i], &item[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
int put = dp[i-1][j-w[i]] + item[i];
if(w[i] > j) dp[i][j] = dp[i-1][j];
else {
dp[i][j] = max(put, dp[i-1][j]);
}
}
}
cout << dp[n][k];
}