https://www.acmicpc.net/problem/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
🔔 문제 :
(1<= N <= 100)N개의 물건이 있습니다.
각 물건은 무게 (1<= W <= 100,000) W와 가치 (0<= V <= 1,000)V를 지닙니다. 하지만 최대 (1<=K<= 100,000) K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있습니다.
이때, 넣을 수 있는 물건들의 가치의 최댓값을 출력하는 문제입니다.
🔔 Kick Point :
물건을 일렬로 쭈욱 나열한 후에 이 물건을 가져갈 지 말지를 고민하면 되는 문제입니다.
예를 들어 {A,B,C,D} 라는 이름의 물건이 있습니다. 각 물건에는 (w,v) 가 주어집니다
이때, 물건의 개수 n개라고 정하고 n= 1부터 n=4까지 고민합니다 순서는 A -> B-> C -> D입니다.
n =1 -> A를 넣었을때 가치 , A를 넣지 않았을 때 가치
n =2 -> B를 넣었을때 가치, B를 넣지 않았을 때 가치
... 들을 넣으면서 실제로 무게에 따른 가치를 적어가면 됩니다.
즉 DP[n(물건을 고려한 수)][w(넣을 수 있는 배낭의 무게)] 를 Bottom-up 방식으로 올려갈 것입니다
이는 점화식으로
DP[i][j] = max(DP[i-1][j] , DP[i-1][j- w] + v) 를 고려하면 됩니다.
🔔 Code :
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
vector<pair<int, int>> v(n+1);
for (int i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j - v[i].first >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second);
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][k];
}
