C#实现0-1背包算法遇问题：数组越界或结果为0

我帮你拆解下代码里的核心问题，以及对应的修复方案：

问题1：数组索引越界的根源 #

你的代码里，k从0循环到n（也就是物品总数3），但当k >= 1时直接用k访问s[k]和v[k]是错误的——C#数组是0基索引，s和v的有效索引范围是0到2（对应3个物品）。当k=3时，s[3]就会触发"Index was outside the bounds of the array"错误。

正确的做法是：当处理第k个物品（从1开始计数）时，用k-1去访问数组里的对应元素。

问题2：循环范围错误导致结果未更新 #

你的内层循环条件是for (int r = 0; r < w; r++)，这意味着你只计算了背包容量从0到w-1的情况，而最后返回的G[n, w]（容量为w的场景）从来没被赋值过，一直是默认的0。需要把循环条件改成r <= w，才能覆盖到目标容量的计算。

额外说明：当前测试用例的特殊性 #

你现在的测试用例里，所有物品的重量（60、100、120）都大于背包容量50，所以即使代码修复了，返回结果还是0——这是正确的，因为确实装不下任何物品。可以换个测试用例验证，比如把背包容量改成100，就能看到正确的计算结果。

修正后的完整代码 #

static int Knapsack(int n, int w, int[] s, int[] v) 
{
    int[,] G = new int[n+1, w+1]; 
    
    for (int k = 0; k <= n; k++) 
    {
        // 修正循环条件：覆盖到容量为w的情况
        for (int r = 0; r <= w; r++) 
        {
            if (r == 0 || k == 0) 
                G[k, r] = 0;
            // 修正数组索引：用k-1访问物品的重量和价值
            else if (s[k-1] <= r) 
                G[k, r] = Math.Max(G[k-1, r], v[k-1] + G[k-1, r - s[k-1]]);
            else 
                G[k, r] = G[k-1, r];
        }
    }
    return G[n, w]; 
}

static void Main(string[] args) 
{
    int[] s = { 60, 100, 120}; 
    int[] v = { 10, 20, 30 }; 
    int w = 100; // 改成能装下物品的容量，验证计算结果
    int n = s.Length; 
    Console.WriteLine(Knapsack(n, w, s, v)); // 此时会返回20，对应选择重量100、价值20的物品
}

验证修改效果 #

• 修正后不会再触发数组越界错误；
• 当背包容量设置为160时，代码会返回30（选择重量60+100的物品，总价值10+20=30，和第三个物品价值一致）；
• 完全符合0-1背包的动态规划逻辑。

内容的提问来源于stack exchange，提问作者Ekli