浅谈java实现背包算法(0-1背包问题)
作者:java林森 发布时间:2022-04-28 15:23:43
标签:java,背包算法
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
0
投稿
猜你喜欢
- 被kafka-client和springkafka版本坑上周刚刚欢天喜地的在linux上部了kafka,这周打算用spring-boot框架
- 前言Java虽然五脏俱全但总有软肋,譬如获取CPU等硬件信息,当然我们可以通过JNI调用C/C++来获取,但对于对C/C++和Windows
- 一.以springboot为例,建立代码1.IExecCommandServer:public interface IExecCommand
- Mybatis 复杂对象resultMap数据对象含有普通属性,一对一对象,一对多对象(2种情况:单一主键和复合主键)下面是resultMa
- 本文实例总结了java判断字符串是否为数字的方法。分享给大家供大家参考,具体如下:方法一:用JAVA自带的函数public static b
- 1.基本语法key: value;kv之间有空格大小写敏感使用缩进表示层级关系缩进不允许使用tab,只允许空格缩进的空格数不重要,只要相同层
- 该工具包含是封装了jedis,包含redis.properties和jedisPool,序列化使用的是protostuff,map类型操作使
- 本文实例为大家分享了Android TextView实现跑马灯效果的具体代码,供大家参考,具体内容如下当Layout中只有一个TextVie
- 此解决方案是针对window的,因为日志默认保存路径在C盘,linux忽略。学习RocketMQ过程中,总是出现com.alibaba.ro
- 今天重新装了编译器,结果崩无极限,真是日了狗了了。刚刚才知道问题在哪边。好了,说正事,对于ios开发我没接触,不是很了解,百度了半天,差不多
- 本文实例讲述了Java设计模式之抽象工厂模式。分享给大家供大家参考,具体如下:具体工厂类:生产创建某一类具体产品对象。抽象产品类可以使用接口
- 自定义工具类PropertyUtil,并在该类的static静态代码块中读取properties文件内容保存在static属性中以供别的程序
- 一、平衡二叉树的定义平衡二叉树是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二叉排序树。意思是说,
- MultipartResolver和ServletFileUpload冲突如果同时使用了MultipartResolver 和Servlet
- 一:什么是SparkSQL?(一)SparkSQL简介Spark SQL是Spark的一个模块,用于处理结构化的数据,它提供了一个数据抽象D
- spring mvc中的@PathVariable是用来获得请求url中的动态参数的,十分方便,复习下: @Controller publ
- 一. * 搭建及配置1 . * 简介 * 是架设在局域网的一种特殊的远程仓库,目的是代理远程仓库及部署第三方构件。有了 * 之后,当 Maven
- 参数传递即将参数传输到程序后台中,后台可能做一些处理,然后再将内容存入数据库之类嗒!参数传递的方法较多,一一说明如下。1、Action中直接
- 前言最近写了一篇博客是关于使用Jenkins来构建SVN+Maven项目 ,这里使用的的代码版本工具是SVN,但是事实上也有很多公司使用GI
- 本文实例为大家分享了Java实现坦克大战小游戏的具体代码,供大家参考,具体内容如下创作背景:n年前的学期末课题设计,从b站上学的,一个代码一