题解 | 【模板】01背包 c#

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {
        var inputNums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int n = inputNums[0];
        int v = inputNums[1];
        List<int> itemsVolume = new List<int>();
        List<int> itemsValue = new List<int>();
        for(int i = 0; i< n; i++)
        {
            List<int> inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
            // itemsVolume[i] = inputs[0];
            // itemsValue[i] = inputs[1];
            itemsVolume.Add(inputs[0]);
            itemsValue.Add(inputs[1]);
        }
        zeroOneBackpack(n,v,itemsVolume,itemsValue,out int r1, out int r2);
        Console.WriteLine(r1);
        Console.WriteLine(r2);
    }
    public static void zeroOneBackpack(int n, int v, List<int> itemsVolume,
                                       List<int> itemValue, out int ans1, out int ans2) {
        // 方案1
        int[,] dp1 = new int[n+1,v+1];//这表示前i个物品，容量j下的最大价值，其实01背包就是把一个容量为j的背包看成了从容量为0到容量为j的j+1个子背包，算出每个子背包能装的最大价值，就可以最终得出容量为j的背包能装的最大价值，所以这个数组的意思就是列出了能装0个到n个物品的，容量为0到v的背包，计算每个背包的dp
        
        //装的物品数量为0的背包的价值一定都为0
        for(int j = 0; j<v+1; j++)
        {
            dp1[0,j] = 0;
        }

        for(int i = 1; i < n+1; i++)
        {
            for(int j =1; j< v+1; j++)
            {
                //不将第i个物品放入,则当前dp为dp1[i-1,j] 
                dp1[i,j] = dp1[i-1,j];//必须用dp1[i,j]来承接，因为当 j < itemsVolume[i-1] 时，应该继承 dp1[i-1,j]
                //如果将第i个物品放入（前提是背包容量足够），此时背包中的剩余容量为j - volumes[i-1]，所以剩余容量下的最大价值为dp[i-1][j - volumes[i-1]]，所以当前容量下的最大价值为剩余容量下的最大价值+当前放入物品的价值dp[i-1][j - volumes[i-1]] + values[i-1]
                if (j >= itemsVolume[i - 1])
                {
                    long valueIfTakeCurrentItem = dp1[i - 1, j - itemsVolume[i-1]] + itemValue[i-1]; //注意，这里的第i个物品的volume放在itemsVolume中的第i-1个，这和dp的索引有差别，因为dp的0索引代表物品数量为0的背包（value也是同理）
                    //对比放第i个物品和不放第i个物品时背包的值，取最大的座位dp[i,j]的值
                    dp1[i,j] = Math.Max((int)valueIfTakeCurrentItem,dp1[i,j]);
                }
                
            }
        }
        ans1 = 0;//最后取结果就是取能放i个物品的背包中的最大值，因为当然是能放的物品越多背包的值才能越大
        for(int j = 0; j< v+1; j++)
        {
            ans1 = Math.Max(dp1[n,j],ans1);
        }

        //方案2:  方案2 = 方案1 + 不可达状态标记 + 直接取 dp[n][V]
        const int INFS = -1000_000_000;
        int[,] dp2 = new int[n+1,v+1] ;
        // 初始化：只有容量0时可达（相当于容量为0的背包恰好背0装满），其他不可达
        dp2[0,0] = 0;
        for (int j = 1; j < v+1; j++)
        {
            dp2[0,j] = INFS; //
        }

        for(int i = 1; i< n+1; i++)
        {
            for (int j = 1; j < v+1; j++)
            {
                //不放入当前物品,继承上一个状态（上一个状态也有可能是INFS）
                dp2[i,j] = dp2[i-1,j];
                //如果放入当前物品,且放入后的上一个状态（背包剩余容量的dp的状态）不为INFS
                if(j >= itemsVolume[i-1] && dp2[i-1, j- itemsVolume[i-1]] != INFS)
                {
                    int valueIfTakeCurrentItem = itemValue[i-1] + dp2[i-1, j- itemsVolume[i-1]];
                    dp2[i,j] = Math.Max(dp2[i,j],valueIfTakeCurrentItem);
                }

            }
        }

        ans2 = dp2[n,v] == INFS ? 0 :dp2[n,v];
    }
}