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
[ 문제풀이 ]
dp문제 중에 쉬운 편에 속하고, 매우 직관적인 문제입니다.
2차원 배열을 만들고 각 행과 열에 i번째 물건까지 넣을 수 있고, 배낭에 넣을 수 있는 최대 무게가 j일 때, 최댓값을 경신해나가면 dp [ N ][ K ]가 배낭에 넣을 수 있는 최댓값이 됩니다.
예제를 예로 들면 물건들의 정보는 다음과 같습니다.
다음 2차원 배열에서 i 는 물건의 개수를 의미하고, j는 가방의 무게를 의미합니다.
먼저 i가 1일 때 가방의 무게가 최소 6일 때 물건을 담을 수 있습니다. 따라서 표를 채우면 다음과 같은 결과를 얻을 수 있습니다.
그리고 i가 2일 때 표는 다음과 같습니다.
그리고 문제의 핵심 부분인 i가 3일 때 표입니다.
무게가 7일 때 dp[dp [ 3 ][ 7 ] = dp [ 3 - 1 ][ 7 - 3 ] + 6로 경신되는 것을 볼 수 있습니다. 가방의 무게가 7일 때 지금까지는 최댓값이 13이었지만 위의 결과를 통해 14로 경신되었습니다. 이와 같이 점화식을 세워보면 다음과 같습니다.
dp [ i ][ j ] = max( dp [ i - 1 ][ j - W] + V, dp [ i - 1 ][ j ] )
표를 마지막까지 채워보면,
위와 같은 결과를 얻을 수 있고, 결과적으로 dp[ N ][ K ]를 출력해주면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> using namespace std; struct stuff { int W; int V; }; int N, K; stuff arr[101]; int dp[101][100001]; int main() { cin >> N >> K; for (int i = 1; i <= N; i++) { cin >> arr[i].W >> arr[i].V; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= K; j++) { if (j >= arr[i].W) { dp[i][j] = max(dp[i - 1][j - arr[i].W] + arr[i].V, dp[i - 1][j]); } else { dp[i][j] = dp[i - 1][j]; } } } cout << dp[N][K]; } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 1865번 - 웜홀 (C++) (0) | 2022.06.10 |
|---|---|
| [ 백준 ] 1238번 - 파티 (C++) (0) | 2022.06.09 |
| [ 백준 ] 9663번 - N-Queen (C++) (0) | 2022.06.07 |
| [ 백준 ] 1504번 - 특정한 최단 경로 (C++) (0) | 2022.06.06 |
| [ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++) (0) | 2022.06.05 |