个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Java背包问题求解实例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和无限背包，这里主要讨论01背包，即每个物品最多放一个。而无限背包可以转化为01背包.
先说一下算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果:
（1），v[i][0]=v[0][j]=0; （2），v[i][j]=v[i-1][j] 当w[i]>j （3），v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 当j>=w[i] 。
好的，我们的算法就是基于此三个结论式.
1、01背包:
1、二维数组法 。
|
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
|
public
class
sf {
public
static
void
main(String[] args) {
// TODO Auto-generated method stub
int
[] weight = {
3
,
5
,
2
,
6
,
4
};
//物品重量
int
[] val = {
4
,
4
,
3
,
5
,
3
};
//物品价值
int
m =
12
;
//背包容量
int
n = val.length;
//物品个数
int
[][] f =
new
int
[n+
1
][m+
1
];
//f[i][j]表示前i个物品能装入容量为j的背包中的最大价值
int
[][] path =
new
int
[n+
1
][m+
1
];
//初始化第一列和第一行
for
(
int
i=
0
;i<f.length;i++){
f[i][
0
] =
0
;
}
for
(
int
i=
0
;i<f[
0
].length;i++){
f[
0
][i] =
0
;
}
//通过公式迭代计算
for
(
int
i=
1
;i<f.length;i++){
for
(
int
j=
1
;j<f[
0
].length;j++){
if
(weight[i-
1
]>j)
f[i][j] = f[i-
1
][j];
else
{
if
(f[i-
1
][j]<f[i-
1
][j-weight[i-
1
]]+val[i-
1
]){
f[i][j] = f[i-
1
][j-weight[i-
1
]]+val[i-
1
];
path[i][j] =
1
;
}
else
{
f[i][j] = f[i-
1
][j];
}
//f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]);
}
}
}
for
(
int
i=
0
;i<f.length;i++){
for
(
int
j=
0
;j<f[
0
].length;j++){
System.out.print(f[i][j]+
" "
);
}
System.out.println();
}
int
i=f.length-
1
;
int
j=f[
0
].length-
1
;
while
(i>
0
&&j>
0
){
if
(path[i][j] ==
1
){
System.out.print(
"第"
+i+
"个物品装入 "
);
j -= weight[i-
1
];
}
i--;
}
}
}
|
输出:
|
1
2
3
4
5
6
7
|
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4 4 4 4 4 4
0 0 0 4 4 4 4 4 8 8 8 8 8
0 0 3 4 4 7 7 7 8 8 11 11 11
0 0 3 4 4 7 7 7 8 9 11 12 12
0 0 3 4 4 7 7 7 8 10 11 12 12
第4个物品装入 第3个物品装入 第1个物品装入
|
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V).
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值.
伪代码如下:
|
1
2
3
|
for
i=
1
..N
for
v=V..
0
f[v]=max{f[v],f[v-c[i]]+w[i]};
|
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的.
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同.
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解.
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0.
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了.
2、一维数组法（无须装满） 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public
class
sf {
public
static
void
main(String[] args) {
// TODO Auto-generated method stub
int
[] weight = {
3
,
5
,
2
,
6
,
4
};
//物品重量
int
[] val = {
4
,
4
,
3
,
5
,
3
};
//物品价值
int
m =
12
;
//背包容量
int
n = val.length;
//物品个数
int
[] f =
new
int
[m+
1
];
for
(
int
i=
0
;i<f.length;i++){
//不必装满则初始化为0
f[i] =
0
;
}
for
(
int
i=
0
;i<n;i++){
for
(
int
j=f.length-
1
;j>=weight[i];j--){
f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
}
}
for
(
int
i=
0
;i<f.length;i++){
System.out.print(f[i]+
" "
);
}
System.out.println();
System.out.println(
"最大价值为"
+f[f.length-
1
]);
}
}
|
输出 。
|
1
2
|
0 0 3 4 4 7 7 7 8 10 11 12 12
最大价值为12
|
3、一维数组法（必须装满） 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public
class
sf {
public
static
void
main(String[] args) {
// TODO Auto-generated method stub
int
[] weight = {
3
,
5
,
2
,
6
,
4
};
//物品重量
int
[] val = {
4
,
4
,
3
,
5
,
3
};
//物品价值
int
m =
12
;
//背包容量
int
n = val.length;
//物品个数
int
[] f =
new
int
[m+
1
];
for
(
int
i=
1
;i<f.length;i++){
//必装满则f[0]=0,f[1...m]都初始化为无穷小
f[i] = Integer.MIN_VALUE;
}
for
(
int
i=
0
;i<n;i++){
for
(
int
j=f.length-
1
;j>=weight[i];j--){
f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
}
}
for
(
int
i=
0
;i<f.length;i++){
System.out.print(f[i]+
" "
);
}
System.out.println();
System.out.println(
"最大价值为"
+f[f.length-
1
]);
}
}
|
输出 。
|
1
2
|
0 -2147483648 3 4 3 7 6 7 8 10 11 12 11
最大价值为11
|
2、完全背包 。
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大.
但我们有更优的O(VN)的算法.
O(VN)的算法 。
这个算法使用一维数组，先看伪代码:
|
1
2
3
|
for
i=
1
..N
for
v=
0
..V
f[v]=max{f[v],f[v-cost]+weight}
|
你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public
class
test{
public
static
void
main(String[] args){
int
[] weight = {
3
,
4
,
6
,
2
,
5
};
int
[] val = {
6
,
8
,
7
,
5
,
9
};
int
maxw =
10
;
int
[] f =
new
int
[maxw+
1
];
for
(
int
i=
0
;i<f.length;i++){
f[i] =
0
;
}
for
(
int
i=
0
;i<val.length;i++){
for
(
int
j=weight[i];j<f.length;j++){
f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
}
}
System.out.println(f[maxw]);
}
}
|
输出 。
|
1
|
|
总结 。
以上就是本文关于Java背包问题求解实例代码的全部内容，希望对大家有所帮助。如有不足之处，欢迎留言指出，小编会及时回复大家并进行修改，努力给广大编程工作及爱好者提供更优质的文章和更好的阅读体验。感谢朋友们对本站的支持！ 。
原文链接：http://blog.csdn.net/ls5718/article/details/52227908 。
最后此篇关于Java背包问题求解实例代码的文章就讲到这里了,如果你想了解更多关于Java背包问题求解实例代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger，它应该
我是 Java 新手。 我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做，因为我只是得到了想要的外观第一的)。这是我的主课 代码: packag
好的，今天我在接受采访，我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题，我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样？”。她是想骗我吗？还是我的一生都
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
如果我将使用 Java 5 代码的应用程序编译成字节码，生成的 .class 文件是否能够在 Java 1.4 下运行？ 如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索，似乎 Scala 也不支持无符号数据类型。限制是Java和S
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行 最佳答案 通常，字节码无需修改即可在 较新 版本的 Java 上运行。它不会在旧版本上运行，除非您使用特殊参数 (
我有一个关于在命令提示符下执行 java 程序的基本问题。 在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
我已经阅读 StackOverflow 有一段时间了，现在我才鼓起勇气提出问题。我今年 20 岁，目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。 基本上，我有一家提供簿记应用
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序，提示用户输入 1 到 10 之间的任意整数，然后以序数形式显示该整数并附加后缀。 public
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
我想在 GUI 上添加延迟。我放置了 2 个 for 循环，然后重新绘制了一个标签，但这 2 个 for 循环一个接一个地执行，并且标签被重新绘制到最后一个。 我能做什么？ for(int i=0;
我正在对对象 Student 的列表项进行一些测试，但是我更喜欢在 java 类对象中创建硬编码列表，然后从那里提取数据，而不是连接到数据库并在结果集中选择记录。然而，自从我这样做以来已经很长时间了，
我知道对象创建分为三个部分: 声明 实例化 初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化 它必须使用
我有兴趣使用 GPRS 构建车辆跟踪系统。但是，我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗？人们意识到任何问题吗？ 我计划使用 Java/Java EE - 有更好的技术吗？ 如果
我可以通过递归方法反转数组，例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组，我不知道为什么，请帮助我。 public class Recursion { p
有这样的标准方式吗？ 包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器 最后我希望有一个自动构建和集成环境。
我什至不知道这是否可能，我非常怀疑它是否可能，但如果可以，您能告诉我怎么做吗？我只是想知道如何从打印机打印一些文本。 有什么想法吗？ 最佳答案 这里有更简单的事情。 import javax.swin
我是一名优秀的程序员,十分优秀！