백준 12865 [평범한 배낭]

문제

흔히 냅색 알고리즘이라고 불리는 문제이고 Dynamic Programing중 대표 문제이다

아이디어

물품을 1번/1,2번/1,2,3번 ~~ 물품까지 고려한다고 생각하면서 나아간다고 했을때 무게가 0부터 최대일때까지 새롭게 고려사항이 되는 물품을 넣는것과 넣지않는것 으로 구분할 수 있다.

W가 최대 수용 무게 N이 N번째 물품까지 고려 라고 하자. DP에는 현재 가치값이 저장된다

물건(무게,가치) (6,13),(4,8),(3,6),(5,12)

무게가 0 일때는 아무것도 담을수없고,0번쨰 물품은 존재하기 않기에 0으로 초기화한다

W ,I	0	1	2	3	4
0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0
6	0
7	0

1번째 물품까지 고려한다고 하자.1번째 물품의 무게는 6이고 가치가 13이므로

W ,I	0	1	2	3	4
0	0	0	0	0	0
1	0	0
2	0	0
3	0	0
4	0	0
5	0	0
6	0	13
7	0	13

1번째 까지는 물품이 한개밖에 없으므로 넣을수 있으면 무조건 넣는것이 이득이다

이제 2번쨰 물품까지 고려한다고 하자.

W ,I	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0
2	0	0	0
3	0	0	0
4	0	0	8
5	0	0	8
6	0	13	13
7	0	13	13

2번째 물품은 무게가 4이므로,

(W<4)일때는 dp[i-1][w]를 가져온다

2번째 물품이 들어갈 자리가 없으므로 고려한거랑 안한거랑 가치값은 변함이 없기때문에

(W>=4)일때는 2번째 물품이 들어갈 수 있으므로 이전에 있던것을 뺴고 넣는게 이득인지 판단해야 한다

넣지않는것은 고려하지 않을때랑 똑같으므로 위와 마찬가지로 dp[i-1][w]이다
넣을때는 2번쨰 물품의 무게만큼을 확보해야 하므로 -> dp[i-1][w-4]
이 식에 2번째 물품의 가치를 넣어주어야 한다 -> dp[i-1][w-4]+8

넣은것과 넣지않는것중 더 높은 값으로 갱신한다
max(dp[i-1][w],dp[i-1][w-4]+8)
이를 토대로 표를 채우면

W ,I	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	13	13	13	13
7	0	13	13	14	14

코드

package dynamicProgramming

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

/**
 * N개의 물건 W무게 V가치
 *최대 K만큼
 * 가치의 최댓값
 * https://www.acmicpc.net/problem/12865
 */
fun main(){
    val br = System.`in`.bufferedReader()
    val line1 = StringTokenizer(br.readLine())

    val N = line1.nextToken().toInt()
    val K = line1.nextToken().toInt()


    //무게 value
    val item = Array(N+1) { Array(2){0} }
    for(i in 1 until N+1){
        val line = StringTokenizer(br.readLine())
        item[i][0] = line.nextToken().toInt()
        item[i][1] = line.nextToken().toInt()
    }

    //N은 가방 index,K가 무게
   val dp = Array(N+1){Array(K+1){0}}
    for(i in 1 until  N+1){
        for(w in 1 until K+1){
            //현재 물건을 넣을 수 있다.
            if(item[i][0]<=w){
                dp[i][w] = kotlin.math.max(dp[i-1][w],dp[i-1][w-item[i][0]]+item[i][1])
            }
            //현재 물건을 넣을 수 없다
            else{
                dp[i][w] = dp[i-1][w]
            }
        }
    }

    println(dp[N][K])
}