«   2022/10   »
            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          
Archives
Today
0
Total
96,326
관리 메뉴

차근차근

[백준 12865] 평범한 배낭 본문

대학교/Algorithm

[백준 12865] 평범한 배낭

SWKo 2020. 9. 11. 21:53

0. 제목

  • 백준 12865 평범한 배낭
  • BOJ 12865 평범한 배낭
  • 파이썬 12865 평범한 배낭
  • Python 12865 평범한 배낭

1. 문제

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


2. 풀이

  • dp[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치
  • 각 물품의 번호 i에 따라서 dp[i][j]를 갱신한다.
  • 1부터 k까지 증가하는 변수 j가 입력된 무게보다 작은 경우에는 전에 입력된 가치인 dp[i-1][j]를 그대로 가져온다.
  • j가 입력된 무게보다 크거나 같은 경우에는 max(dp[i - 1][j], dp[i - 1][j - w] + v) 의 값이 dp[i][j]의 값이 된다.
  • 이 문제에서는 (4, 8), (3, 6)일 때가 가치합의 최댓값인데, 세번째 물건인 (3,6)이 들어왔을 때 dp[3][7] = 14 로 갱신이 된다.
  • 반복문을 마친 후 dp[n][k]이 가치합의 최댓값이 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
n, k = map(int, input().split())
dp = [[0* (k + 1for _ in range(n + 1)]
 
for i in range(1, n + 1):
    w, v = map(int, input().split())
    for j in range(1, k + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            
print(dp[n][k])
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 9251] LCS  (0) 2020.09.12
[백준 11053] 가장 긴 증가하는 부분 수열  (0) 2020.09.12
[백준 1904] 01타일  (0) 2020.09.10
[백준 1325] 효율적인 해킹  (0) 2020.09.09
[백준 1012] 유기농 배추  (0) 2020.09.08
0 Comments
댓글쓰기 폼