网站做内嵌,wordpress打开要10秒,网站优化排名软件,有谁做彩票网站吗0-1背包的问题背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品#xff0c;每种物品都有自己的重量和价格#xff0c;在限定的总重量内#xff0c;我们如何选择#xff0c;才能使得物品的总价格最高。问题的名称来源于如何选择最合适的…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] }。public class Bag {static class Item {// 定义一个物品String id; // 物品idint size 0;// 物品所占空间int value 0;// 物品价值static Item newItem(String id, int size, int value) {Item item new Item();item.id id;item.size size;item.value value;return item;}public String toString() {return this.id;}}static class OkBag { // 定义一个打包方式List Items new ArrayList();// 包里的物品集合OkBag() {}int getValue() {// 包中物品的总价值int value 0;for (Item item : Items) {value item.value;}return value;};int getSize() {// 包中物品的总大小int size 0;for (Item item : Items) {size item.size;}return size;};public String toString() {return String.valueOf(this.getValue()) ;}}// 可放入包中的备选物品static Item[] sourceItems { Item.newItem(4号球, 4, 5), Item.newItem(5号球, 5, 6), Item.newItem(6号球, 6, 7) };static int bagSize 10; // 包的空间static int itemCount sourceItems.length; // 物品的数量// 保存各种情况下的最优打包方式 第一维度为物品数量从0到itemCount,第二维度为包裹大小从0到bagSizestatic OkBag[][] okBags new OkBag[itemCount 1][bagSize 1];static void init() {for (int i 0; i bagSize 1; i) {okBags[0][i] new OkBag();}for (int i 0; i itemCount 1; i) {okBags[i][0] new OkBag();}}static void doBag() {init();for (int iItem 1; iItem itemCount; iItem) {for (int curBagSize 1; curBagSize bagSize; curBagSize) {okBags[iItem][curBagSize] new OkBag();if (sourceItems[iItem - 1].size curBagSize) {// 当前物品大于包空间.肯定不能放入包中.okBags[iItem][curBagSize].Items.addAll(okBags[iItem - 1][curBagSize].Items);} else {int notIncludeValue okBags[iItem - 1][curBagSize].getValue();// 不放当前物品包的价值int freeSize curBagSize - sourceItems[iItem - 1].size;// 放当前物品包剩余空间int includeValue 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);}}}}}public static void main(String[] args) {Bag.doBag();for (int i 0; i Bag.itemCount 1; i) {// 打印所有方案中包含的物品for (int j 0; j Bag.bagSize 1; j) {System.out.print(Bag.okBags[i][j].Items);}System.out.println();}for (int i 0; i Bag.itemCount 1; i) {// 打印所有方案中包的总价值for (int j 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);}}以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持脚本之家。
