首页 > 代码库 > 算法随笔一（背包问题）

算法随笔一（背包问题）

2024-08-25 19:28:33   217人阅读

今天逛园子，偶然看到了“背包问题”，于是上网找了下相关资料，并写了个简单的实现方案。

何为背包问题？

简单理解，就是给了一堆物品跟一个包，每个物品都有相应的重量和价值，包有自己的承重。我们要做的就是在包的承重范围内，往包里装下价值总量最高的物品。

如何解决背包问题？

一般采用递归的方法，对每次放入物品进行数学建模。每次放入物品都会有两种选择（前提是该物品能放入）：

1. 放入该物品，那么问题转换成，减去该物品的重量，包剩余的容量最多能装下多少价值的物品。

2. 不放入该物品，那么问题转换成，算上该物品的重量，包的容量最多能装下多少价值的物品

为了方便理解，可以参考以下表格（首行为包的容量）：

重量 0 1 2 3 4 5 6 7 8 9 10 价值
2 0 0 5 5 5 5 5 5 5 5 5 5
5 0 0 5 5 5 6 6 11 11 11 11 6
3 0 0 5 5 6 6 6 11 11 11 12 1
7 0 0 5 5 6 6 6 16 16 21 21 16
8 0 0 5 5 6 6 6 16 16 21 21 10

 

 

 

 

 

拿数据部分，第四行第八列的数据来说

如果放入物品三，则最高价值为1(物品三价值)+5（承重为4时的最高价值）=6。

如果不放入物品三，则最高价值为11（承重为7时放入前面物品的最高价值）

代码如下：

物品类

public class BagItem
{
    public int Weight { get; set; }
    public int Value { get; set; }
}

背包类

public class Bag
{
    private List<BagItem> _items;
    private int _capacity;

    public Bag(List<BagItem> items,int capacity)
    {
        this._items = items;
        this._capacity = capacity;
    }

    public int CalculateMaxValue()
    {
        int n = _items.Count;
        int[,] array = new int[n + 1, _capacity + 1];
        for (int i = 0; i < n + 1; i++)
        {
            array[i, 0] = 0;
        }
        for (int i = 0; i < _capacity + 1; i++)
        {
            array[0, i] = 0;
        }

        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < _capacity + 1; j++)
            {
                if (_items[i-1].Weight > j)
                {
                    array[i, j] = array[i - 1, j];
                }
                else
                {
                    array[i, j] = Math.Max((_items[i-1].Value + array[i - 1, j-_items[i-1].Weight]), array[i - 1, j]);
                }
            }
        }

        return array[n, _capacity];
    }
}

背包问题的实现就写到这。

算法随笔一（背包问题）


联系
我们