首页 > 代码库 > 算法随笔一(背包问题)
算法随笔一(背包问题)
今天逛园子,偶然看到了“背包问题”,于是上网找了下相关资料,并写了个简单的实现方案。
何为背包问题?
简单理解,就是给了一堆物品跟一个包,每个物品都有相应的重量和价值,包有自己的承重。我们要做的就是在包的承重范围内,往包里装下价值总量最高的物品。
如何解决背包问题?
一般采用递归的方法,对每次放入物品进行数学建模。每次放入物品都会有两种选择(前提是该物品能放入):
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]; } }
背包问题的实现就写到这。
算法随笔一(背包问题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。