https://www.acmicpc.net/problem/12865
유명한 0/1 knapsack problem 다이나믹 프로그래밍 문제입니다.
사실 저도 못 풀어서 결국에는 검색을 통해 알게 된 문제...
https://gsmesie692.tistory.com/113
위 주소는 knapsack problem을 잘 정리되어있어 참고하는데 도움을 받았습니다.
dp[i][j]에서 i는 물건 i번째까지 가방에 넣은 것을 의미하고 j는 배낭에 담을수 있는 무게를 뜻합니다.
그러므로 물건을 담는 경우와 담지 않는 경우 2가지를 생각해야합니다.
위 문제의 예제에서 첫번 째 물건(무게 6 가치 13)
첫 번째 물건만 담았을 때 최대 무게에 대한 최대 가치입니다.
두번 째 물건(무게 4 가치 8)
두 번째 물건만 담았을 때 최대 무게에 대한 최대 가치입니다. ( 두 번째 물건만입니다. 혼동하지마세요)
즉, j가 4나 5인 경우 가치가 8인 물건을 담을 수 있지만 j가 6이나 7인 경우 첫 번째 물건 13이 최대 가치입니다.
세 번째 물건은 무게가 3, 가치가 6입니다.
무게가 3이므로 i가 3이고 j가 3일때, 6의 최대 가치를 갖고
j가 4나 5인 경우 두 번째 물건의 무게가 4이므로 해당하는 가치가 들어갑니다.
j가 6이나 7인 경우에도 마찬가지로 첫 번째 물건의 가치가 가장 높기때문에 표시합니다.
하지만, 이렇게 하면 틀립니다.
여기서 j가 7인 경우에는 두 번째 물건의 무게가 4, 세 번째 물건의 무게가 3이므로 j가 7인 자리에는
각각의 가치를 더한 값인 14가 들어온다는 것이죠.
즉 이것을 점화식으로 나타낸다면 dp[i][j] = max(dp[i][j], dp[i-1][j-w]+v)로 나타낼 수 있다는 것이죠.
네 번째 물건을 입력하게 되면 이런 식으로 표가 작성됩니다.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int N;
int K;
int W;
int V;
int dp[101][100001] ={0};
int maxi = 0;
cin>>N>>K;
for(int i = 1; i <= N; i++){
cin>>W>>V;
for(int j = 1; j <= K; j++){
dp[i][j] = max(dp[i][j], dp[i-1][j]);
if(j>=W){
dp[i][j] = max(dp[i][j], dp[i-1][j-W]+V);
maxi = max(maxi, dp[i][j]);
}
}
}
cout<<maxi;
return 0;
}
'BOJ 백준 > Class 4' 카테고리의 다른 글
백준 15663번, N과 M(9) (C,C++) (0) | 2022.01.27 |
---|---|
백준 17070번, 파이프 옮기기 1(C, C++) (0) | 2022.01.24 |
백준 1865번, 웜홀(C, C++) (0) | 2022.01.21 |
백준 1238번, 파티(C, C++) (0) | 2022.01.21 |
백준 1932번, 정수 삼각형(C, C++) (0) | 2022.01.21 |