-
12865 평범한 배낭알고리즘/백준 2019. 3. 26. 15:07
1. 문제
2. 코드
1234567891011121314151617181920212223242526272829#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int W[101];int V[101];int dp[101][100001];int main() {int N, K;scanf("%d %d", &N, &K);for (int i = 1; i <= N; i++)scanf("%d %d", &W[i], &V[i]);for (int i = 1; i <= N; i++) {for (int j = 1; j <= K; j++) {if (W[i] <= j) {int free_w = j - W[i];dp[i][j] = max(dp[i - 1][j], dp[i - 1][free_w] + V[i]);}else {dp[i][j] = dp[i - 1][j];}}}printf("%d", dp[N][K]);}cs 3. 후기
dp배열은 다음과 같이 출력된다.
0 0 0 0 0 13 13
0 0 0 8 8 13 13
0 0 6 8 8 13 14
0 0 6 8 12 13 14
w[i]와 v[i]의 i를 하나씩 늘려가면서 최댓값을 찾아낸다.
'알고리즘 > 백준' 카테고리의 다른 글
5557 1학년 (0) 2019.03.27 1495 기타리스트 (0) 2019.03.26 11066 파일합치기 (0) 2019.03.25 11058 크리보드 (0) 2019.03.21 2294 동전 2 (0) 2019.03.19