[12865] - 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

지금까지 풀었던 동적 계획법 메모이제이션 문제들과 비슷한 거 같은데 표를 만들어서 푸는 냅색문제라 신기했다.

 

첫 접근 방식

회의실 배정 문제처럼 무게, 가중치를 작은 순서대로 정렬 후 가방에 들어갈 수 있다면 추가 해주는 식으로 풀었다가 틀렸다.

- 중간에서부터 골랐을 때가 처음 부터 골랐을 때보다 가중치가 더 높은 경우가 있어 실패.

 

문제 풀이

행의 개수는 물건의 개수, 열의 개수는 가방의 무게 1~입력받은 수 까지 설정하고 풀었다. (이전 것과 더해주어야 하니 둘다 0이 아닌 1에서 부터 시작하여 인덱스가 입력받은거 보다 1씩 큼)

• ex)이전 물건의 무게가 2, 가중치가 3,  현재 물건의 무게가 5, 가중치가 10

물건 \ 무게	0	1	2	3	4	5	6
2, 3	0	0	3	3	6	6	9
5, 10	0	0	3	3	6	10	10

현재 무게가 5 이상일 때 부터 무게가 들어가니, 전 물건의 5일 때의 가중치, 전 물건의 무게 0의 가중치에 현재 물건의 가중치를 더한 값을 비교하여 큰값을 표에 넣는다.

•  연두색 + 현재 물건 가중치, 남색 비교 -> 6보다는 0+10이 더크니 주황색은 10.

이런 작업을 반복하다 보면 표의 가장 오른쪽 하단은 가중치가 가장 크게 들어가므로 그 값이 답이된다.

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace Baekjoon.Gold
{
    class _12865
    {
        static void Main(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[][] things = new int[n[0]][];
            for(int i = 0; i<n[0]; i++)
                things[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            //0으로 초기화 - 행: 물건의 개수, 열: 배낭의 무게
            int[][] backpack = new int[n[0]+1][];
            for (int i = 0; i <=n[0]; i++)
                backpack[i] = Enumerable.Repeat(0, n[1]+1).ToArray();

            for (int i = 1; i<=n[0]; i++)
            {
                for(int j = 1; j<=n[1]; j++)
                {
                    //물건의 무게가 배낭에 들어가면
                    if (things[i - 1][0] <= j)
                        //현 무게에 해당하는 전물건의 가치, 무게가(현가방무게 - 현물건무게)인 가치 + 현물건의 가치 비교
                        backpack[i][j] = Math.Max(backpack[i - 1][j], backpack[i - 1][j - things[i - 1][0]] + things[i - 1][1]);
                    //안들어가면 그냥 전물건의 가치 적용
                    else
                        backpack[i][j] = backpack[i - 1][j];
                }
            }
            Console.WriteLine(backpack[n[0]][n[1]]);
        }
    }
}