2. 0-1 背包問題

# 題目給的 w(i) 一定是從 1 開始，故實做 dp 時，取 weights, values 都要 -1

Console.Write("  輸入物品的總數量: ");
int n = int.Parse(Console.ReadLine());

Console.Write("  輸入背包的最大承載量 (10 的倍數): ");
int W = int.Parse(Console.ReadLine()) / 10;

Console.WriteLine("輸入各物品的重量與價值:");

int[] weights = new int[n];
int[] values = new int[n];
for (int i = 1; i <= n; i++)
{
    Console.Write($"物品 {i} - 重量: ");
    weights[i - 1] = int.Parse(Console.ReadLine()) / 10;
    Console.Write($"物品 {i} - 價值: ");
    values[i - 1] = int.Parse(Console.ReadLine());
}

int[,] c = new int[n + 1, W + 1];

for (int i = 0; i <= n; i++)
{
    for (int w = 0; w <= W; w++)
    {
        if (i == 0 || w == 0) continue; // defaults to 0, we just have to continue.
        if (weights[i - 1] > w)
            c[i, w] = c[i - 1, w];
        if (i > 0 && w >= weights[i - 1]) c[i, w] = Math.Max(values[i - 1] + c[i - 1, w - weights[i - 1]], c[i - 1, w]);
    }
}

for (int i = 0; i <= n; i++)
{
    for (int w = 0; w <= W; w++)
    {
        Console.Write($"{c[i, w]}\t");
    }
    Console.WriteLine();
}