C#实现动态规划解决0-1背包问题

0-1 背包问题核心逻辑

0-1 背包问题是动态规划的典型应用场景。目标是在不超过背包总容量的前提下，从一组不可分割的物品中选取若干件，使得它们的总价值最大。算法的核心在于状态转移方程：对于每一个容量 i 和每一件物品 j，如果装入物品 j 能获得比不装更高的价值，则更新当前容量下的最大价值。

C# 实现步骤

第1步：定义数据与环境

首先需要引入必要的命名空间，并定义物品列表。本例中包含5件物品，每件物品具有固定的重量（Size）和价值（Value），以及一个固定的背包总容量（Capacity）。

• 名称空间：System, System.Collections.Generic, System.Linq, System.Text
• 背包容量：capacity = 16
• 物品重量：{ 3, 4, 7, 8, 9 }
• 物品价值：{ 4, 5, 10, 11, 13 }

第2步：初始化状态数组

创建两个关键数组来辅助计算：

1. totval：长度为 capacity + 1，用于存储当前容量下能获得的“最大总价值”。初始默认值为0。
2. best：长度为 capacity + 1，用于记录在达到某个容量最佳解时，最后加入的那件物品的索引，以便后续追溯选中的物品（本示例主要关注最大价值输出）。

第3步：执行动态规划迭代

通过嵌套循环遍历所有物品和所有可能的容量。对于第 j 件物品，检查从 0 到总容量 capacity 的每一个位置 i：

• 如果当前容量 i 大于等于物品 j 的重量 size[j]。
• 比较“不装这件物品时的价值”（即 totval[i] 原值）与“装了这件物品后的价值”（即 totval[i - size[j]] + values[j]）。
• 如果后者更大，则更新 totval[i] 为新的最大值，并将 best[i] 标记为当前物品索引 j。

// 利用动态规划解决0-1背包问题
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Knapsack_problem
{
    class Program
    {
        static void Main()
        {
            int i;
            int capacity = 16;
            int[] size = new int[] { 3, 4, 7, 8, 9 };
            // 5件物品每件大小分别为3, 4, 7, 8, 9 
            //且是不可分割的 0-1 背包问题
            int[] values = new int[] { 4, 5, 10, 11, 13 };
            // 5件物品每件的价值分别为4, 5, 10, 11, 13
            int[] totval = new int[capacity + 1];
            // 数组totval用来存贮最大的总价值
            int[] best = new int[capacity + 1];
            // best 存贮的是当前价值最高的物品
            int n = values.Length;
            for (int j = 0; j <= n - 1; j++)
                for (i = 0; i <= capacity; i++)
                    if (i >= size[j])
                        if (totval[i] < (totval[i - size[j]] + values[j]))
                // 如果当前的容量减去J的容量再加上J的价值比原来的价值大，
                //就将这个值传给当前的值
                        {
                            totval[i] = totval[i - size[j]] + values[j];
                            best[i] = j; // 并把j传给best
                        }
            Console.WriteLine("背包的最大价值: " + totval[capacity]);
            // Console.WriteLine("构成背包的最大价值的物品是: " );
            // int totcap = 0;
            // while (totcap <= capacity)
            // {
            //  Console.WriteLine("物品的大小是：" + size[best[capacity - totcap]]);
            //  for (i = 0; i <= n-1; i++)
            //  totcap += size[best[i]];
            // }
        }
    }
}

结果与分析

运行上述代码后，程序将在控制台输出背包能容纳的最大价值。根据给定的数据，物品总容量限制为16，算法会计算出在此限制下可放入物品的最高价值总和。该代码展示了基础的一维数组优化版动态规划思路，空间复杂度为 O(Capacity)，时间复杂度为 O(N * Capacity)。

总结

以上就是 C# 使用动态规划解决 0-1 背包问题的详细内容，更多关于 C# 算法设计、动态规划应用的相关资料请关注本站其它相关文章！