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); } }
|
忍者必须死34399账号登录版 最新版v1.0.138v2.0.72
下载勇者秘境oppo版 安卓版v1.0.5
下载忍者必须死3一加版 最新版v1.0.138v2.0.72
下载绝世仙王官方正版 最新安卓版v1.0.49
下载Goat Simulator 3手机版 安卓版v1.0.8.2
Goat Simulator 3手机版是一个非常有趣的模拟游
Goat Simulator 3国际服 安卓版v1.0.8.2
Goat Simulator 3国际版是一个非常有趣的山羊模
烟花燃放模拟器中文版 2025最新版v1.0
烟花燃放模拟器是款仿真的烟花绽放模拟器类型单机小游戏,全方位
我的世界动漫世界 手机版v友y整合
我的世界动漫世界模组整合包是一款加入了动漫元素的素材整合包,
我的世界贝爷生存整合包 最新版v隔壁老王
我的世界MITE贝爷生存整合包是一款根据原版MC制作的魔改整