- 浏览: 585876 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
好文章,来自:http://blog.csdn.net/shuqin1984/archive/2010/09/02/5859223.aspx
0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。
值得提及的一个问题是,在用 JAVA 实现时, 是按算法模型建模,还是用对象模型建模呢? 如果用算法模型,那么背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。
给定背包:
[weight: 2 value: 12]
[weight: 1 value: 10]
[weight: 3 value: 20]
[weight: 2 value: 15]
给定总承重: 5
-------- 该背包问题实例的解: ---------
最优值:37
最优解【选取的背包】:
[[weight: 2 value: 15], [weight: 1 value: 10], [weight: 2 value: 12]]
最优值矩阵:
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
下载源码
0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。
值得提及的一个问题是,在用 JAVA 实现时, 是按算法模型建模,还是用对象模型建模呢? 如果用算法模型,那么背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。
public class Knapsack { /** 背包重量 */ private int weight; /** 背包物品价值 */ private int value; /** * 构造器 */ public Knapsack(int weight, int value) { this.value = value; this.weight = weight; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public String toString() { return "[weight: " + weight + " " + "value: " + value + "]"; } } import java.util.ArrayList; /** * 求解背包问题: * 给定 n 个背包,其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn * 要放入总承重为 totalWeight 的箱子中, * 求可放入箱子的背包价值总和的最大值。 * * NOTE: 使用动态规划法求解 背包问题 * 设 前 n 个背包,总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n]; * 求解最优值: * 1. 若 j < wn, 则 : v[n,j] = v[n-1,j]; * 2. 若 j >= wn, 则:v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。 */ public class KnapsackProblem { /** 指定背包 */ private Knapsack[] bags; /** 总承重 */ private int totalWeight; /** 给定背包数量 */ private int n; /** 前 n 个背包,总承重为 totalWeight 的最优值矩阵 */ private int[][] bestValues; /** 前 n 个背包,总承重为 totalWeight 的最优值 */ private int bestValue; /** 前 n 个背包,总承重为 totalWeight 的最优解的物品组成 */ private ArrayList<Knapsack> bestSolution; public KnapsackProblem(Knapsack[] bags, int totalWeight, int n) { this.bags = bags; this.totalWeight = totalWeight; this.n = n; if (bestValues == null) { bestValues = new int[n+1][totalWeight+1]; } if (bestSolution == null) bestSolution = new ArrayList<Knapsack>(); } /** * 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题 * */ public void solution() { System.out.println("给定背包:"); for(Knapsack b: bags) { System.out.println(b); } System.out.println("给定总承重: " + totalWeight); // 求解最优值 for (int j = 0; j <= totalWeight; j++) { for (int i = 0; i <= n; i++) { if (i == 0 || j == 0) { bestValues[i][j] = 0; } else { // 如果第 i 个背包重量大于总承重,则最优解存在于前 i-1 个背包中, // 注意:第 i 个背包是 bags[i-1] if (j < bags[i-1].getWeight()) { bestValues[i][j] = bestValues[i-1][j]; } else { // 如果第 i 个背包不大于总承重,则最优解要么是包含第 i 个背包的最优解, // 要么是不包含第 i 个背包的最优解, 取两者最大值,这里采用了分类讨论法 // 第 i 个背包的重量 iweight 和价值 ivalue int iweight = bags[i-1].getWeight(); int ivalue = bags[i-1].getValue(); bestValues[i][j] = Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]); } // else } //else } //for } //for // 求解背包组成 int tempWeight = totalWeight; for (int i=n; i >= 1; i--) { if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) { bestSolution.add(bags[i-1]); tempWeight = totalWeight - bags[i-1].getWeight(); } } } /** * 获得前 n 个背包, 总承重为 totalWeight 的背包问题的最优解值 * 调用条件: 必须先调用 solution 方法 * */ public int getBestValue() { bestValue = bestValues[n][totalWeight]; return bestValue; } /** * 获得前 n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵 * 调用条件: 必须先调用 solution 方法 * */ public int[][] getBestValues() { return bestValues; } /** * 获得前 n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵 * 调用条件: 必须先调用 solution 方法 * */ public ArrayList<Knapsack> getBestSolution() { return bestSolution; } } public class TestKnapsack { public static void main(String[] args) { Knapsack[] bags = new Knapsack[] { new Knapsack(2,12), new Knapsack(1,10), new Knapsack(3,20), new Knapsack(2,15) }; int totalWeight = 5; int n = bags.length; KnapsackProblem kp = new KnapsackProblem(bags, totalWeight, n); kp.solution(); System.out.println(" -------- 该背包问题实例的解: --------- "); System.out.println("最优值:" + kp.getBestValue()); System.out.println("最优解【选取的背包】: "); System.out.println(kp.getBestSolution()); System.out.println("最优值矩阵:"); int[][] bestValues = kp.getBestValues(); for (int i=0; i < bestValues.length; i++) { for (int j=0; j < bestValues[i].length; j++) { System.out.printf("%-5d", bestValues[i][j]); } System.out.println(); } } }
给定背包:
[weight: 2 value: 12]
[weight: 1 value: 10]
[weight: 3 value: 20]
[weight: 2 value: 15]
给定总承重: 5
-------- 该背包问题实例的解: ---------
最优值:37
最优解【选取的背包】:
[[weight: 2 value: 15], [weight: 1 value: 10], [weight: 2 value: 12]]
最优值矩阵:
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
下载源码
- knaps.zip (2.5 KB)
- 下载次数: 0
发表评论
-
龙抬头
2014-11-10 15:06 554... -
求推箱子的最小步数(java)
2014-05-06 08:32 3674题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2989POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3155回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1778一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1875很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5829Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3991一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1212一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 1969先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2268一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2226继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4909深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1404如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1107例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1468广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1644有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2067再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2224凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1073最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1691677
NULL 博文链接:https://128kj.iteye.com/blog/1688560
NULL 博文链接:https://128kj.iteye.com/blog/1692204
NULL 博文链接:https://128kj.iteye.com/blog/1688360
NULL 博文链接:https://128kj.iteye.com/blog/1689477
NULL 博文链接:https://128kj.iteye.com/blog/1689243
NULL 博文链接:https://128kj.iteye.com/blog/1688531
NULL 博文链接:https://128kj.iteye.com/blog/1689359
基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf
这些算法按照难度和类型进行分类,包括数组、字符串、递归、排序、搜索、动态规划等多个领域。每个算法都提供了详细的解析和代码实现,帮助读者深入理解算法的原理和应用。 对于初学者,这些算法可以帮助他们掌握...
每个案例都是经过精心筛选的,具有代表性和实用性,是算法学习和实践的绝佳素材。 每个案例都配有详细的解析和注释,包括算法思路、实现代码和复杂度分析,帮助读者深入理解算法的实现细节和时间空间复杂度,并掌握...
这本书包含了各种经典的算法问题,涵盖了排序、查找、递归、动态规划、图论等多个领域,每个案例都经过精心挑选,具有代表性和实用性,是C语言算法学习的绝佳素材。 每个案例都配有详细的解析和注释,包括算法思路...
PID控制算法应用讲解,另外还包含了自动驾驶学习资料的获取: 涵盖感知,规划和控制,ADAS,传感器; 1. apollo相关的技术教程和文档; 2.adas(高级辅助驾驶)算法设计(例如AEB,ACC,LKA等) 3.自动驾驶鼻祖...
经典算法题每日演练——第十五题 并查集 经典算法题每日演练——第十四题 Prim算法 经典算法题每日演练——第十三题 赫夫曼树 经典算法题每日演练——第十二题 线段树 经典算法题每日演练——第十一题 Bitmap算法 ...
1 6 5 动态规划算法 20 1 6 6 用整数编码集合 21 1 6 7 二分查找 23 1 7 建议 25 1 8 走得更远 27 第 2 章 字符串 28 2 1 易位构词 28 2 2 T9:9 个按键上的文字 29 2 3 使用字典树进行拼写纠正 31 2 4 KMP(Knuth-...
1规划、二次规划、拉格朗曰法、起作用集算法、路径跟踪法、粒子群优化算法、基本粒子群算法、带压缩因子的粒子群算法、权重改进的粒子群算法、线性递减权重法、自适应权重法、随机权重法、变学习因子的粒子群算法、...
蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例 基于人工蚁群优化的矢量量化码书设计算法 具有自适应杂交特征的蚁群算法 蚁群算法在原料矿粉混匀优化中的应用 基于多Agent的蚁群算法在车间动态调度中的...
针对装备精确保障任务规划中任务时序逻辑约束和资源占用冲突等问题,建立以时效优先为目标的数学模型,提出基于多维动态列表规划和混沌蝙蝠算法的混合任务规划方法.通过多维动态列表规划选择处理的任务,设计具有自适应...
算法学习的五个内容 如何设计算法 运用一些基本设计策略规划算法 如何表示算法 用恰当的方式表示算法 如何确认算法 算法正确性的证明(算法确认algorithm validation) 如何分析算法 通过时间和空间复杂度的分析,...