[TIL] 130 [C#] 배낭, DP

---

배낭 DP

---

배낭문제

문제 예시
배낭에 물건을 넣을 때 배낭에 들어갈 수 있는 무게(k), 로 최대가치로 물건(n)개 배낭에 담기.

예시

int[n,k] dp
1 ~ n번째 물건을 k이하로 담을 때 최대의 가치 = dp[n,k]

/* 입력
4 7     // (n, k)
6 13    // (k, value) - 1번째 물건의 정보
4 8     // 2번째 
3 6     // 3
5 12    // 4
*/

class Program
{
    static void Main()
    {
        {
            var sw = new StreamWriter(Console.OpenStandardOutput());

            //int T = Convert.ToInt32(Console.ReadLine());
            int[] inputArr = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
            int n = inputArr[0];
            int k = inputArr[1];

            var objs = new (int k , int v)[n+1];    // 튜플로 물건의 무게,가치 저장
            int[,] dp = new int[n + 1, k + 1];

            for (int i = 1; i <= n; i++)
            {
                int[] obj = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
                objs[i].k = obj[0];
                objs[i].v = obj[1];
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= k; j++)
                {
                    if (objs[i].k <= j) // dp[i,j] 1 ~ i 번째 물건을 j이하로 담을 때 최대의 가치 = dp[i,j]  
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - objs[i].k] + objs[i].v);
                        // dp[i,j] => 
                        // 이전 물건까지 가치 
                        // (이전 물건까지의 무게 + 현재물건의 무게) 가 배낭 중량(j) 보다 작을 때 의 가치
                        // 둘중 큰값.
                    }
                    else
                    {
                        dp[i, j] = dp[i - 1, j];
                    }
                }
            }

            sw.WriteLine($"{dp[n,k]}");
            sw.Flush(); sw.Close();
        }
    }
}

DP

3. 배낭 담기 DP

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= k; j++)
    {
        if (objs[i].k <= j) // dp[i,j] 1 ~ i 번째 물건을 j이하로 담을 때 최대의 가치 = dp[i,j]  
        {
            dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - objs[i].k] + objs[i].v);
            // dp[i,j] => 
            // 이전 물건까지 가치 
            // (이전 물건까지의 무게 + 현재물건의 무게) 가 배낭 중량(j) 보다 작을 때 의 가치
            // 둘중 큰값.
        }
        else
        {
            dp[i, j] = dp[i - 1, j];
        }
    }
}

---

잡담, 일기?

배낭문제 dp

---