C# 背包问题（简单）

背包问题（简单）

假设：物品有20个，每个的重量不一样，且不可分割，现在需要装入到重量为30Kg的背包中。
1、求出最少需要多个背包？
2、每个背包的装的是哪几个物品？

本人才疏学浅，求示例个C#代码~

using System;
using System.Collections.Generic;

namespace KnapsackProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            // 物品重量数组
            int[] weights = new int[] { 2, 3, 4, 5, 9, 7, 8, 10, 1, 6, 11, 12, 14, 15, 16, 18, 19, 20, 21, 22 };
            // 背包容量
            int capacity = 30;

            int[] dp = new int[capacity + 1];
            List<List<int>> items = new List<List<int>>();

            for (int i = 0; i < dp.Length; i++)
            {
                items.Add(new List<int>());
            }

            for (int i = 0; i < weights.Length; i++)
            {
                for (int j = capacity; j >= weights[i]; j--)
                {
                    if (dp[j] < dp[j - weights[i]] + 1)
                    {
                        dp[j] = dp[j - weights[i]] + 1;
                        items[j].Clear();
                        items[j].Add(i);
                        items[j].AddRange(items[j - weights[i]]);
                    }
                }
            }

            Console.WriteLine($"需要 {dp[capacity]} 个背包");
            Console.WriteLine($"每个背包装的物品编号分别为：");

            for (int i = 0; i < items[capacity].Count; i++)
            {
                Console.Write($"{items[capacity][i]} ");
            }
        }
    }
}

注：这里使用动态规划求解背包问题，dp数组表示背包容量为j时，最多能装多少个物品。items列表记录每个容量下装的物品编号列表。

示例：
public class Item
{
    public int Weight { get; set; }
}
public class Bag
{
    public int Capacity { get; set; }
    public List<Item> Items { get; set; }
    public int UsedCapacity { get; set; }
}
public class GreedyAlgorithm
{
    public List<Bag> Greedy(List<Item> items, int capacity)
    {
        // 根据重量将物品从大到小排序
        items.Sort((item1, item2) => item2.Weight - item1.Weight);
        // 初始化背包列表
        List<Bag> bags = new List<Bag>();
        // 遍历物品
        for (int i = 0; i < items.Count; i++)
        {
            Item item = items[i];
            // 如果当前物品的重量大于背包的容量，则新建一个背包
            if (item.Weight > capacity)
            {
                bags.Add(new Bag
                {
                    Capacity = capacity,
                    UsedCapacity = 0,
                    Items = new List<Item> { item }
                });
            }
            // 否则尝试将物品放入已有的背包中
            else
            {
                // 遍历已有的背包，尝试将物品放入
                foreach (Bag bag in bags)
                {
                    // 如果背包的剩余容量足够放入当前物品，则放入背包
                    if (bag.Capacity - bag.UsedCapacity >= item.Weight)
                    {
                        bag.Items.Add(item);
                        bag.UsedCapacity += item.Weight;
                        break;
                    }
                }
            }
        }
        return bags;
    }
}

using System;

namespace KnapsackProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] weights = {2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; // 物品重量
            int n = weights.Length; // 物品数量
            int capacity = 30; // 背包容量
            int[,] dp = new int[n + 1, capacity + 1]; // 状态数组

            // 初始化状态数组
            for (int j = 0; j <= capacity; j++)
            {
                dp[0, j] = int.MaxValue; // 背包容量为 j 时，前 0 个物品最少需要的背包数为 int.MaxValue
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j <= capacity; j++)
                {
                    dp[i, j] = dp[i - 1, j]; // 不选第 i 个物品

                    if (j >= weights[i - 1] && dp[i - 1, j - weights[i - 1]] != int.MaxValue)
                    {
                        dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j - weights[i - 1]] + 1); // 选第 i 个物品
                    }
                }
            }

            // 最少需要的背包数
            int minBags = dp[n, capacity];
            Console.WriteLine("最少需要的背包数：" + minBags);

            // 求解背包装的物品
            int[] bags = new int[minBags];
            int k = capacity;
            for (int i = n; i > 0 && k > 0; i--)
            {
                if (dp[i, k] == dp[i - 1, k]) // 第 i 个物品未选
                {
                    continue;
                }

                bags[--minBags] = i - 1; // 第 minBags 个背包装的物品是 i-1

                k -= weights[i - 1]; // 背包剩余容量
            }

            // 输出每个背包装的物品
            for (int i = 0; i < bags.Length; i++)
            {
                Console.Write("第 " + (i + 1) + " 个背包装的物品：");
                for (int j = 0; j < n; j++)
                {
                    if (bags[i] == j)
                    {
                        Console.Write(j + " ");
                    }
                }
                Console.WriteLine();
            }
        }
    }
}