如何使用C#编写背包问题算法

来源：这里教程网时间：2026-02-21 16:31:41 作者：

如何使用c#编写背包问题算法

如何使用C#编写背包问题算法

背包问题（Knapsack Problem）是一个经典的组合优化问题，它描述了一个给定容量的背包以及一系列物品，每个物品都有自己的价值和重量。目标是找到一种最佳策略，使得在不超过背包容量的情况下，装入背包的物品总价值最大。

在C#中，可以通过动态规划方法来解决背包问题。具体实现如下：

using System;
namespace KnapsackProblem
{
    class Program
    {
        static int Knapsack(int[] weights, int[] values, int capacity, int n)
        {
            int[,] dp = new int[n + 1, capacity + 1];
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= capacity; j++)
                {
                    if (i == 0 || j == 0)
                        dp[i, j] = 0;
                    else if (weights[i - 1] <= j)
                        dp[i, j] = Math.Max(values[i - 1] + dp[i - 1, j - weights[i - 1]], dp[i - 1, j]);
                    else
                        dp[i, j] = dp[i - 1, j];
                }
            }
            return dp[n, capacity];
        }
        static void Main(string[] args)
        {
            int[] weights = { 5, 3, 4, 2 };
            int[] values = { 60, 50, 70, 30 };
            int capacity = 8;
            int n = weights.Length;
            int maxValue = Knapsack(weights, values, capacity, n);
            Console.WriteLine("背包能装入的最大价值为：" + maxValue);
        }
    }
}

以上代码中，我们定义了一个名为