最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
浅谈java实现背包算法(0-1背包问题)
时间:2022-06-29 01:23:42 编辑:袖梨 来源:一聚教程网
0-1背包的问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。
publicclassBag { staticclassItem {// 定义一个物品 String id;// 物品id intsize =0;// 物品所占空间 intvalue =0;// 物品价值 staticItem newItem(String id,intsize,intvalue) { Item item =newItem(); item.id = id; item.size = size; item.value = value; returnitem; } publicString toString() { returnthis.id; } } staticclassOkBag {// 定义一个打包方式 List- Items =newArrayList
- ();// 包里的物品集合 OkBag() { } intgetValue() {// 包中物品的总价值 intvalue =0; for(Item item : Items) { value += item.value; } returnvalue; }; intgetSize() {// 包中物品的总大小 intsize =0; for(Item item : Items) { size += item.size; } returnsize; }; publicString toString() { returnString.valueOf(this.getValue()) +" "; } } // 可放入包中的备选物品 staticItem[] sourceItems = { Item.newItem("4号球",4,5), Item.newItem("5号球",5,6), Item.newItem("6号球",6,7) }; staticintbagSize =10;// 包的空间 staticintitemCount = sourceItems.length;// 物品的数量 // 保存各种情况下的最优打包方式 第一维度为物品数量从0到itemCount,第二维度为包裹大小从0到bagSize staticOkBag[][] okBags =newOkBag[itemCount +1][bagSize +1]; staticvoidinit() { for(inti =0; i < bagSize +1; i++) { okBags[0][i] =newOkBag(); } for(inti =0; i < itemCount +1; i++) { okBags[i][0] =newOkBag(); } } staticvoiddoBag() { init(); for(intiItem =1; iItem <= itemCount; iItem++) { for(intcurBagSize =1; curBagSize <= bagSize; curBagSize++) { okBags[iItem][curBagSize] =newOkBag(); if(sourceItems[iItem -1].size > curBagSize) {// 当前物品大于包空间.肯定不能放入包中. okBags[iItem][curBagSize].Items.addAll(okBags[iItem -1][curBagSize].Items); }else{ intnotIncludeValue = okBags[iItem -1][curBagSize].getValue();// 不放当前物品包的价值 intfreeSize = curBagSize - sourceItems[iItem -1].size;// 放当前物品包剩余空间 intincludeValue = sourceItems[iItem -1].value + okBags[iItem -1][freeSize].getValue();// 当前物品价值+放了当前物品后剩余包空间能放物品的价值 if(notIncludeValue < includeValue) {// 放了价值更大就放入. okBags[iItem][curBagSize].Items.addAll(okBags[iItem -1][freeSize].Items); okBags[iItem][curBagSize].Items.add(sourceItems[iItem -1]); }else{// 否则不放入当前物品 okBags[iItem][curBagSize].Items.addAll(okBags[iItem -1][curBagSize].Items); } } } } } publicstaticvoidmain(String[] args) { Bag.doBag(); for(inti =0; i < Bag.itemCount +1; i++) {// 打印所有方案中包含的物品 for(intj =0; j < Bag.bagSize +1; j++) { System.out.print(Bag.okBags[i][j].Items); } System.out.println(""); } for(inti =0; i < Bag.itemCount +1; i++) {// 打印所有方案中包的总价值 for(intj =0; j < Bag.bagSize +1; j++) { System.out.print(Bag.okBags[i][j]); } System.out.println(""); } OkBag okBagResult = Bag.okBags[Bag.itemCount][Bag.bagSize]; System.out.println("最终结果为:"+ okBagResult.Items.toString() + okBagResult); } }
|
相关文章
- 《燕云十六声》红尘无眼完成图文攻略 12-25
- 《燕云十六声》阴阳如影完成图文攻略 12-25
- 《燕云十六声》悬檐之下四架椽屋图文攻略 12-25
- 《燕云十六声》2024最新公测时间介绍 12-25
- 《燕云十六声》有没有藏宝阁 12-25
- 《燕云十六声》制作公司介绍 12-25