在Java中实现背包问题

摘 要：背包问题在数据结构算法中是最基础的一环，随着Java学习的深入，势必对某些基础算法编程实现，以提高应用Java类的层次，在这里通过采用图表的形式，先分析各种数据的组合，再编程实现背包问题。

关键词：背包；规化；最佳解

1 背包问题概述

假设一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内总价最多的物品，假设装入水果的编号、单价与重量如表1-1所示。

表1-1 水果详单

首先对该背包问题进行分析，然后再编写程序，找出答案。

2 背包问题分析

背包问题属于最佳化的问题，要解决最佳化问题可以使用动态规划方案，从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到就是最佳解。以背包问题为例，这里使用两个阵列value与item，value表示目前的最佳解所得的总价，item表示最后一个放至背包的水果，假设有负重为1～8 kg的背包8个，并对每个背包求其最佳解。逐步将水果放入背包中，并求该阶段的最佳解。

放入李子的求最佳解过程如表1-2所示

表1-2 李子的求解过程

放入苹果的求最佳解过程如表1-3所示

表1-3 苹果的求解过程

放入橘子的求最佳解过程如表1-4所示

表1-4 橘子的求解过程

放入草莓的求最佳解过程如表1-5所示

表1-5 草莓的求解过程

放入甜瓜的求最佳解过程如表1-6所示

表1-6 甜瓜的求解过程

由最后一个表格可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤的水果，所以必须看背包负重7公斤时的最佳解，最后一个放入的是2号，也就是橘子，现在背包剩下负重5公斤，所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重0公斤，无法再放入水果，所以求出最佳解，具体答案如下表1-7所示。

表1-7 程序的运行结果

3 程序描述

背包问题算法的核心程序如下：

public static void main（String[ ] args）

final int MAX_WEIGHT=8；

final int MIN_WEIGHT=1；

int[ ] key=new int[MAX_WEIGHT+1]；

FruitInBag FruitInBags[ ]={ new FruitInBag（“李子”，4，4500），…}；

for（int i=0；i< FruitInBags.length；i++） {

for（int s= FruitInBags[i].getweight（ ）；s

int p=s- FruitInBags[i].getweight（ ）；

int newvalue=value[p]+ FruitInBags[i].getprice（ ）；

if （newvalue>value[s]） {

value[s]=newvalue；

key[s]=i；

4 结束语

数据结构的相关算法在Java程序中都可实现，而为算法编写程序可以检验Java类的实用性，因Java在游戏的开发中备受青睐，而游戏的设计又建立在各种算法的基础上，所以打好基础就应该认真推敲算法在Java程序的实现，这样在学到Java高级应用的时候可以得心应手，体系结构也会更清晰。

参考文献

[1] 张昆.Java程序员面试指南[M].北京：电子工业出版社，2010

[2] 顾婷.基于Java的数据结构算法演示系统的研究[J].信息与电脑，2011（3）

[2] 李荣荣.Java程序算法可视化表示与研究[J].浙江工业大学，2012（3）