`

Java 背包算法计算从数组中找若干个数使其最接近某个数

    博客分类:
  • Java
阅读更多
背包的算法的动态方式如下:
f(i,w) = max{ f(i-1,w), f(i-1,v-weight[i])+value[i] }


状态转移方程理解如下:

f(i,w)表示前i个物体面对容量为w时背包的最大价值,weight[i]代表物体i的重量(即重量),value[i]代表物体i的价值;如果第i个物体不放入背包,则背包的最大价值等于前i-1个物体面对容量v的最大价值;如果第i个物体选择放入,则背包的最大价值等于前i-1个物体对容量w-weight [i]的最大价值加上物体i的价值value[i]。


综上,第i件物品要么选,要么不选。
1)如果不选,则第i件物品放w容量的最优值等于第i-1件物品放w容量的最优值;
2)如果i选,则第i件物品放w-weight容量的最优值再加value[i]的值。

现在我们的问题是:在一个数组中有若个数据,找出最接近所有数据10%的值?而且我们的实际情况是数组中存在的是实数,物品只有三百个左右,而待查找的数是几十万的情况。

做法:
1)所有的数据进行格式化处理,剔除小于100的数,实数四舍五入变正整数;
2)待查找的数降100倍,同时格式化的数据也进行降100倍处理,这样可以大大节省内存空间。

核心代码如下:
public static void beiBao() {
		// 背包的容量大小,最大的数据为50w,10%就是5w,再降100倍,即为500
		int dp[] = new int[501];
		char state[][] = new char[deal_Array.length][501]; /* 记录路径的二维数组 */
		int i, j;
		int M = 49602 / 100; // 待查找近似值
		/* 01背包 */
		for (i = 0; i < deal_Array.length; ++i) {
			for (j = M; j >= deal_Array[i]; --j) {
				int tmp = dp[j - deal_Array[i]] + deal_Array[i];
				if (tmp > dp[j]) {
					dp[j] = tmp;
					state[i][j] = 1;
				}
			}
		}
		i = deal_Array.length; // 第几个商品
		j = M;// 当前背包容量
		System.out.println("============================");
		while ((--i) >= 0) {
			if (state[i][j] == 1) {
				System.out.print(deal_Array[i] + " ");
				j -= deal_Array[i];
			}
		}
}
分享到:
评论

相关推荐

    用回溯算法解决0/1背包问题

    目标是从这`n`个物品中选择若干个放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。 #### 二、回溯算法原理 回溯算法是一种通过试探搜索解决问题的方法,它尝试构建问题的所有解,并逐步检查这些...

    0-1背包问题代码

     为此,我们定义一个二维数组,其中每个元素代表一个状态,即前个物体中若干个放入体积为背包中最大价值。数组为:,其中表示前件中若干个物品放入体积为的背包中的最大价值。  ②、初始状态  初始状态为和都为...

    java简单算法

    7. **分治算法**:分治策略将大问题分解为若干个相同或相似的小问题,然后逐个解决。如快速排序、归并排序和大整数乘法等。 8. **数据结构**:Java中的数据结构如数组、链表、栈、队列、树(二叉树、平衡树如AVL、...

    java算法大全(含源码包)

    10. **分治算法**:将大问题划分为若干个相似的小问题,分别解决后再合并,如快速排序、归并排序、大整数乘法等。 通过学习这个Java算法大全,不仅可以掌握各种算法的实现,还能深入理解其背后的逻辑和思想,这对于...

    面试java 常见算法

    Java面试中的算法问题通常涉及到数据结构、排序、搜索、图论等多个方面,是评估候选人编程能力和逻辑思维的重要标准。在准备Java面试时,理解和熟练掌握这些算法至关重要,因为它们不仅体现了程序员的基础技能,还能...

    JAVA经典算法.pdf

    0/1背包问题是指给定一组物品,每种物品都有自己的重量和价值,在限定的总重量内,选择其中若干个(也可以是0个),设计选择方案使得总价值最高。 在代码片段中,定义了一个Fruit类,用于表示每种物品,包含名称、...

    java算法

    在Java编程语言中,算法通常指的是高效地处理数据和执行计算的方法。Java提供了丰富的库和工具来支持各种算法的实现,使得开发者能够用Java解决复杂的问题。 在Java中,算法的应用非常广泛,包括排序、搜索、图论、...

    Java数据结构和算法

    在编程领域,尤其是Java开发中,数据结构和算法是核心基础,它们对于编写高效、可扩展的代码至关重要。本文将深入探讨Java中的数据结构和算法,帮助你提升编程能力。 一、数据结构 数据结构是组织和管理数据的方式...

    实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划)视频

    动态规划是一种解决多阶段决策过程中的最优化问题的方法,其基本思想是将原问题分解为若干个相互重叠的子问题,并保存子问题的解避免重复计算。 **2. 动态规划的基本要素** - **最优子结构**: 问题的最优解包含了其...

    JAVA经典算法

    "JAVA经典算法"这个压缩包文件很可能是汇集了一些在实际开发中常见的、高效的算法实现,对于学习和提升编程技能非常有帮助。以下是对这些算法的详细介绍: 1. **排序算法**:包括快速排序、归并排序、冒泡排序、...

    java常用算法

    2. 分治:分治策略将大问题分解为若干个相同或相似的小问题,分别解决,再合并结果。快速排序、归并排序都是典型的分治算法。 五、动态规划 动态规划是一种通过构建子问题的最优解来解决原问题的算法,常用于背包...

    源代码_背包问题--01背包_

    dp[i][j]的值代表前i个物品中选择若干个(总重量不超过j)的最大价值。初始化时,当没有物品时,背包的最大价值为0,即dp[0][j] = 0。然后,对每个物品,我们有两种选择:包含它或者不包含它。如果包含第i个物品且其...

    java数据结构和算法实现.zip

    Java数据结构和算法实现是一个深度探讨编程基础的重要主题,它涉及到如何高效地组织和操作数据。数据结构是存储和组织数据的方式,而算法是解决问题或执行任务的特定步骤。在这个zip文件中,"ljg_resource1"可能是一...

    算法总结java

    1. 线性查找:线性查找是最简单的查找算法,从数组的一端开始,逐个与目标值比较,直到找到目标值或者搜索完整个数组。 2. 二分查找:二分查找也称为折半查找,适用于已排序的数组。它通过不断将查找区间缩小一半来...

    关于java算法

    Java算法是计算机科学中的核心部分,它涉及到一系列用于解决复杂问题的方法和技术,这些方法和技术在Java编程中扮演着至关重要的角色。Java作为一种广泛使用的面向对象的编程语言,提供了丰富的库和工具来支持算法的...

    蛮力法解决0-1背包问题

    这是因为我们需要尝试所有n个物品的2^n种可能的选中状态,并且对每种状态检查其是否符合背包的容量限制,计算其总价值。 蛮力法的C#实现步骤如下: 1. 定义物品类:每个物品都有一个重量(weight)和一个价值...

    算法设计课外实验.docx

    **实现**:示例代码首先初始化了一个二维数组`m`用于存储子问题的解,其中`m[i][j]`表示前`i`件物品在容量为`j`的背包中的最大价值。然后通过两层循环更新这个数组,最终得到的最大值即为所求。 **特点**:能够有效...

    水库调度程序包含12个动态规划算法的程序代码

    在IT行业中,动态规划是一种非常重要的算法,广泛应用于各种复杂问题的求解,如最短路径、背包问题、任务调度等。在这个特定的压缩包文件中,我们关注的是水库调度程序,它涉及到如何有效地管理水库的水资源,以满足...

    计算机算法设计与分析

    - 在线性时间内找到未排序数组中的中位数或其他序统计量。 **3.10 最接近点对问题** - 寻找一组点中距离最近的两点。 **3.11 循环赛日程表** - 设计合理的比赛日程安排。 #### 四、动态规划 动态规划是一种用于...

Global site tag (gtag.js) - Google Analytics