다이나믹 프로그래밍 한접시

[백준] 12865번: 평범한 배낭 [C#]

NaZZU 2024. 4. 6. 04:03

반례의 예시가 더 이해에 도움이 되어서 반례를 들고왔습니다~

 

배낭에 넣을 물건의 개수 N, 배낭의 최대 무게가 주어지고,

물건의 무게, 가치가 N+1행까지 반복되며 주어집니다.

배낭에 가장 가치있게 물건을 넣을때의 최대 가치를 출력해주면 되는 문제입니다.

 

 

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        //static List<int> stack = new List<int>();
        static int possibility = 0;
        static int pre_i = 0;
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int item = input[0]; // 물건의 개수
            int weight = input[1]; // 배낭에 최대 무게
 
            int[] value = new int[item+1]; // 물건의 가치
            int[] weight_idx = new int[item+1]; // 물건의 무게
 
            int[,] bag = new int[item+1, weight+1]; // 경우의 수들을 보관할 배열
 
            for (int a = 0; a < item; a++)
            {
                int[] input2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                weight_idx[a+1= input2[0];
                value[a+1= input2[1];
            }
 
 
            for (int i = 0; i < bag.GetLength(0); i++) // i번 물건을 넣어보겠다
            {
                for (int j = 0; j < bag.GetLength(1); j++) // j의 무게까지 물건을 넣어보겠다
                {
                    if (i == 0 || j == 0) // 0번째 행과 열에 0을 넣음
                        bag[i, j] = 0; // (무게가 0이거나 가치가 0인 물건은 없으니까!)
                    else if (weight_idx[i] <= j) // 가방에 물건을 넣을 수 있다면
                        bag[i, j] = Math.Max(bag[i - 1, j], value[i] + bag[i-1, (j - weight_idx[i])] );
// 저번 반복의 물건과 (이번에 넣을 물건의 무게 + 남은 무게에 넣을 수 있는 물건의 가치)
// 를 비교해서 큰 값을 넣어준다
                    else
                        bag[i, j] = bag[i-1, j]; // 해당사항이 없다면 저번 반복의 물건을 이번에도 넣어준다
                }
            }
 
            Console.WriteLine(bag[item, weight]); // 마지막(최적)의 물건을 출력해준다
 
        }
    }
}
cs

 

DP의 가장 대표적인 문제인 가방 문제라고합니다.

간단한 문제인데 계속 개념이 헷갈려서 엄청 오래걸렸네요;;