다이나믹 프로그래밍 한접시
[백준] 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의 가장 대표적인 문제인 가방 문제라고합니다.
간단한 문제인데 계속 개념이 헷갈려서 엄청 오래걸렸네요;;
