浅谈java实现背包算法(0-1背包问题)
作者:java林森 时间:2022-04-28 15:23:43
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; // 物品id
int 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<Item> Items = new ArrayList<Item>();// 包里的物品集合
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到bagSize
static 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);
}
}
来源:http://www.cnblogs.com/reachlins/p/6549504.html
标签:java,背包算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java实现的简单猜数字游戏代码
2023-06-17 22:56:22
![](https://img.aspxhome.com/file/2023/6/57606_0s.jpg)
详解Spring ApplicationContext加载过程
2023-07-17 01:07:43
Java中Request请求转发详解
2021-05-25 20:53:42
![](https://img.aspxhome.com/file/2023/8/61538_0s.png)
基于Hadoop实现Knn算法
2023-11-27 04:01:20
![](https://img.aspxhome.com/file/2023/8/60048_0s.jpg)
详解MyBatis配置typeAliases的方法
2023-11-29 06:21:52
SpringBoot参数校验与国际化使用教程
2021-11-13 15:52:21
![](https://img.aspxhome.com/file/2023/8/61568_0s.png)
Android Flutter实现搜索的三种方式详解
2023-07-10 18:00:49
Java使用synchronized实现互斥锁功能示例
2022-10-20 00:47:49
Spring mvc Json处理实现流程代码实例
2023-07-14 21:31:06
如何把char数组转换成String
2023-11-11 07:38:15
jdk8使用stream实现两个list集合合并成一个(对象属性的合并)
2023-08-05 16:49:30
![](https://img.aspxhome.com/file/2023/5/57705_0s.png)
SpringBoot整合之SpringBoot整合MongoDB的详细步骤
2023-11-25 09:55:37
![](https://img.aspxhome.com/file/2023/6/59076_0s.png)
hadoop实现grep示例分享
2023-12-24 05:31:04
Android用过TextView实现跑马灯效果的示例
2023-07-27 11:16:54
Java环境配置原理全面解析
2023-11-23 07:56:48
![](https://img.aspxhome.com/file/2023/5/59925_0s.jpg)
springboot 自定义权限标签(tld),在freemarker引用操作
2023-11-23 06:20:15
![](https://img.aspxhome.com/file/2023/9/59979_0s.jpg)
java获取当前时间的四种方法代码实例
2023-11-28 19:22:53
Java实现去除文档阴影的示例代码
2023-08-31 11:45:48
![](https://img.aspxhome.com/file/2023/5/58415_0s.png)
完美解决springboot中使用mybatis字段不能进行自动映射的问题
2023-07-27 00:41:35
![](https://img.aspxhome.com/file/2023/7/61157_0s.png)
ActiveMQ安装及部署教程图解
2023-11-17 18:01:46
![](https://img.aspxhome.com/file/2023/3/59483_0s.png)