安康做网站,怎样攻击网站,汽车之家官网首页网页,qq空间钓鱼网站制作今天逛园子#xff0c;偶然看到了“背包问题”#xff0c;于是上网找了下相关资料#xff0c;并写了个简单的实现方案。 何为背包问题#xff1f; 简单理解#xff0c;就是给了一堆物品跟一个包#xff0c;每个物品都有相应的重量和价值#xff0c;包有自己的承重。我们…今天逛园子偶然看到了“背包问题”于是上网找了下相关资料并写了个简单的实现方案。 何为背包问题 简单理解就是给了一堆物品跟一个包每个物品都有相应的重量和价值包有自己的承重。我们要做的就是在包的承重范围内往包里装下价值总量最高的物品。 如何解决背包问题 一般采用递归的方法对每次放入物品进行数学建模。每次放入物品都会有两种选择前提是该物品能放入 1. 放入该物品那么问题转换成减去该物品的重量包剩余的容量最多能装下多少价值的物品。 2. 不放入该物品那么问题转换成算上该物品的重量包的容量最多能装下多少价值的物品 为了方便理解可以参考以下表格首行为包的容量 重量012345678910价值20055555555555005556611111111630055666111111121700556661616212116800556661616212110 拿数据部分第四行第八列的数据来说 如果放入物品三则最高价值为1(物品三价值)5承重为4时的最高价值6。 如果不放入物品三则最高价值为11承重为7时放入前面物品的最高价值 代码如下 物品类 public class BagItem
{public int Weight { get; set; }public int Value { get; set; }
} 背包类 public class Bag
{private ListBagItem _items;private int _capacity;public Bag(ListBagItem 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];}
} 背包问题的实现就写到这。转载于:https://www.cnblogs.com/alaskii/p/6142368.html
