- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章浅谈java实现背包算法(0-1背包问题)由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
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] }.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
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实现背包算法(0-1背包问题)的文章就讲到这里了,如果你想了解更多关于浅谈java实现背包算法(0-1背包问题)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我已经用 Scala 中的每一项编写了有界背包问题的答案,并尝试将其转换为 Haskell,结果如下: knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ]
我正在解决这个动态编程问题,并且我一直坚持用 Java 编写迭代解决方案 目标是找到花费 X 美分所需的最少卡路里数。如果我们不能恰好花费 X 美分,那么就没有解决方案。我们给定了 N 个元素,每个元
根据维基百科和我浏览过的其他资源,您需要矩阵m[n][W]; n - 元素数量和 W - 背包的总容量。这个矩阵变得非常大,有时大到无法在 C 程序中处理。我知道动态规划的基础是节省内存时间,但是,有
我发现此代码使用蛮力机制解决背包问题(这主要是为了学习,因此无需指出动态更有效)。我得到了可以工作的代码,并且了解了大部分代码。最多。这是问题: 我注意到这两个条件,我不知道它们如何工作以及为什么在代
我必须实现背包问题的以下变体。背包中的每件元素都有优先级和重量。现在我指定一个权重 X。我必须知道计算权重总和至少为 X 并且具有最低优先级的最小项目集。每个项目只能选择一次。示例: Knap
所以我想知道如何计算背包问题的所有解。也就是说,我有兴趣从一组最大大小为 K 的数字中找出可能的子集数。 例如,我们有一组大小为 {3, 2, 5, 6, 7} 的项目,最大大小为 K = 13。因此
我在执行任务时遇到了问题。我有一个数据库,其中包含所有具有“价格”值的项目。它们连接到不同的“轮次”,“轮次”有一个“总值(value)”,其中这些项目“价格”-值(value)全部放在一起定义了“总
我遇到的问题如下: 给定一个包含 N 个元素的队列,每个元素都有一个重量,以及一个包含 K 个容器的队列。我们需要按照元素来的顺序将元素分成容器。例如,第一个项目只能进入第一个容器,第二个可以进入第一
问题如下: You have n trip lengths in km which should be divided among m number of days such that the max
我昨晚在开发一个应用程序时遇到了一个特定的问题,我确信它可能有一个有效的算法来解决它。谁能推荐一下? 问题: TL;DR:也许图片会有所帮助:http://www.custom-foam-insert
如何获取下拉列表,其中占位符显示“选择类别”作为默认选择? 以下代码没有渲染占位符 $this->crud->addField([ // Select2 'label'
刚刚带背包的新品。我在官方网站上搜索并用谷歌搜索,但没有找到答案 在 laravel 7 中,使用 Backpack 4.1 我的数据模型是:客户有很多地址 关系在客户模型中配置: public fu
据我所知(如果我错了请纠正我),背包只处理 $fillable 字段。整个 laravel 的事情不就是 $fillable 和 $guarded 之间的分离吗? MWE: 在 User.php 中:
看到this之后讲座我创建了以下背包代码。在讲座中,教授说从最优值(19:00 分钟)确定集合很容易,但我找不到如何去做。我在代码中提供了一个将值相加为 21 的示例,我如何根据该值确定集合(在本例中
为什么贪心法适用于连续背包问题而不适用于 0-1 背包问题? 最佳答案 对于连续背包,在最佳解决方案中,您不能有 q > 0 的每单位成本为 c 的元素,同时留下 q' > 0 成本为 c' > c
我在理解动态规划时遇到了一些困难,尽管我已经通读了很多资源试图理解。 我理解使用斐波那契算法给出的动态规划示例。我明白如果你使用分而治之的方法,你最终会多次解决一些子问题,而动态编程通过解决这些重叠的
假设一个经典的 0-1 背包问题,但您可以上溢/下溢背包并受到一些惩罚。每单位溢出(重量超过最大容量)扣除X利润,每单位下溢(重量低于最大容量)扣除Y利润。 我想按利润与重量的比率对所有元素进行排序,
我正在编写具有多个约束的背包 0-1 的变体。除了重量限制外,我还有数量限制,但在这种情况下,我想解决背包问题,因为我的背包中需要恰好有 n 件元素,重量小于或等于 W。我我目前正在为基于 Roset
给定一个无限正整数数组或一个正整数流,找出总和为 20 的前五个数。 通过阅读问题陈述,它首先似乎是 0-1 Knapsack 问题,但我很困惑 0-1 Knapsack algo 可以在流上使用的整
我想解决一个3维背包问题。 我有许多不同宽度、高度、长度和值(value)的盒子。我有一个指定的空间,我想把盒子放在那个空间里,这样我就能获得最优的利润。我想使用暴力来做到这一点。 我正在用 Java
我是一名优秀的程序员,十分优秀!