PS/BOJ
[백준] 12865.cpp : 평범한 배낭
bconfiden2
2020. 8. 29. 12:23
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
- 배낭 문제 , 0/1 Knapsack Problem 과 동일한 유형이다.
- 물건의 갯수를 행으로, 배낭 무게를 0~K 까지 열로 삼은 DP를 활용한다.
- 원래 알고리즘에서는 물건의 갯수를 0~N 까지 전부 배열로 만드는데, 슬라이딩 윈도우 기법을 적용해보았다.
- 이걸 안 찾아보고 혼자서 푸는 사람은 뭐하는 사람일까 싶다..
#include <iostream>
using namespace std;
int n, k;
int w, v;
int dp[2][100001];
int answer;
int main(void)
{
cin >> n >> k;
for(int i = 0 ; i < n ; i++)
{
cin >> w >> v;
for(int j = 1 ; j <= k ; j++)
{
if(j < w) dp[i%2][j] = dp[(i+1)%2][j]; // 배낭에 들어갈 수 없으면 이전 물건 값 그대로
else dp[i%2][j] = max(dp[(i+1)%2][j], dp[(i+1)%2][j - w] + v); // 이전 물건 값과 새롭게 추가한 물건값을 비교해서 더 큰 쪽을 저장
if(dp[i%2][j] > answer) answer = dp[i%2][j]; // 최댓값 갱신
}
}
cout << answer << endl;
}