`
623deyingxiong
  • 浏览: 189938 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

组合问题 之 罗列特定和的数字组合方式

阅读更多
package com.test.algorithm.dp;

import java.util.HashSet;
import java.util.Set;

/**
 * @author hawkinswang
 *
 *         01背包问题:在指定数组中挑选任意组合,让它们的和等于一个特定值,列出所有组合方式
 *         使用动态规划方法解决,状态转移方程:dp[i][j]=dp[i-arr[j]][j-1].add(arr[j])
 *
 */
public class FindComineEqualSum {
    public static void main(String[] args) {
	int[] arr = { 1, 3, 5, 7, 8, 9, 10, 2, 4, 6 };
	int sum = 11;

	Set<String> combines = findCombine(arr, sum);

	for (String combine : combines) {
	    if (combine != null) {
		System.out.println("the result is:" + combine);
	    }
	}
    }

    private static Set<String> findCombine(int[] arr, int sum) {
	Set<String> result = new HashSet<String>();
	Set<String>[][] dp = new HashSet[sum + 1][arr.length + 1];
	int i = 0, j = 0;
	for (j = 0; j < arr.length + 1; j++) {// 当求和为0时,初始化为"";非常重要,这是动态规划数组产生合理组合的基础.
	    dp[0][j] = new HashSet<String>();
	    dp[0][j].add("");
	}

	for (i = 1; i <= sum; i++) {
	    for (j = 1; j <= arr.length; j++) {
		for (int k = 0; k <= j - 1; k++) {
		    if (dp[i][k] != null && dp[i][k].size() > 0) {
			if (dp[i][j] == null) {
			    dp[i][j] = new HashSet<String>();
			}
			dp[i][j].addAll(new HashSet<String>(dp[i][k]));
		    }
		}

		if (i >= arr[j - 1] && dp[i - arr[j - 1]][j - 1] != null) {
		    if (dp[i][j] == null) {
			dp[i][j] = new HashSet<String>();
		    }

		    for (String str : dp[i - arr[j - 1]][j - 1]) {
			dp[i][j].add(str + "," + arr[j - 1]);
		    }
		}
	    }

	    // readArray(dp);
	}

	for (Set<String> Set : dp[sum]) {
	    if (Set != null) {
		result.addAll(Set);
	    }
	}

	return result;
    }

    private static void readArray(String[][] dp) {
	for (String[] arr : dp) {
	    for (String str : arr) {
		System.out.print(str + "/");
	    }
	    System.out.println();
	}
	System.out.println("end");

    }

}
分享到:
评论

相关推荐

    部编版第十二周 简单列举.doc

    当存在特定的限制条件时,如例题4中的数字之和必须大于8,我们需要在罗列过程中注意这些条件,按一定的顺序进行,避免重复和遗漏。 5. **循环赛问题**: 例题5讨论的是循环赛的场次计算。在循环赛中,每个队伍都...

    数学广角.doc

    = 3×2×1=6种排列),以及使用特定数字组成的两位数或三位数问题。 在学习过程中,学生需要培养观察、分析和推理的能力,养成有序思考的习惯。同时,掌握排列与组合的逻辑推理是学习难点,需要通过实践和讨论来...

    数电期末复习罗列知识点以及例题

    在准备数字电子技术(数电)的期末复习时,我们需要关注多个关键知识点和例题,以便有效备考。以下是对这些内容的详细解析: 一、数选器与奇偶校验电路设计 4选1数选器74LS153可以用于实现奇偶校验电路。奇偶校验...

    部编版第38周 最大最小问题.doc

    例如,例题1中要求在图形中填入数字,使得每边7个小三角形内数字之和相等,并求最大和。我们可以通过观察和分析,将最小的数填在中心位置,最大的数填在角上,以此类推,逐步构建出满足条件的最大和。 例题2中涉及...

    数字电子技术基础 第四版

    - **设计简单的数字电路**:通过已知逻辑函数式,可以设计出对应的逻辑电路,实现特定的逻辑运算功能。 - **数字系统分析**:在分析数字系统时,能够将逻辑函数转换为真值表,进而分析系统的逻辑行为。 - **软件仿真...

    部编版第32周 算式谜.doc

    - 在特定条件下,如例题3和训练题,需要考虑数字在不同位置上的组合,以满足等式和特定条件,如横行和竖行的和相等,或者数字的乘积相等。 5. **数字填充策略**: - 例题4中,通过分析0在加减乘法中的特殊角色,...

    罗克韦尔 Bulletin 800F简易样本.pdf

    例如,“FP”代表某种型号的按钮开关,后续的字母和数字组合则标识着具体的尺寸、安装方式、电压等级和电气特性等。在工业自动化的开关选型中,以下几个关键知识点是非常重要的: 1. 开关类型:用户需要根据实际...

    专转本计算机选择题集锦.pdf

    11. 题目61至65中出现了各种数字组合和字母,但无法从片段中明确判断具体的考察内容。 12. 题目67和68中出现了10EH和10DH,这些可能是十六进制数表示的数字,通常用在内存地址或某些寄存器的表示上。 13. 题目70至...

    设备考察报告3篇.pdf

    此外,文档中提到的一些符号和数字的组合,如“80%”、“24(911)”等,很可能是表示某种状态的百分比或与紧急事件相关的代码,例如与911相关的代码可能表示紧急状态或紧急服务的联系方式。而“P12Phoenix”、“P***%...

    Number-theoretic-Methods-in-Statistics 作者:K.-T. FANG

    6. 计算数论:研究数字计算中的问题,特别是在大整数的因式分解、素数检验和计算模算术中,这在密码学和现代统计方法中尤其重要。 7. 组合数学:数论与组合数学有着密切的联系,组合设计和有限几何等领域都可能受益...

    LINGO使用教程(对数学建模的学生很有用)

    这里,`John`、`Jill`等是`students`集的成员,而`1`和`0`分别代表男性和女性,数字代表年龄。 ##### 3.3 注释 使用感叹号(!)开始的行被视为注释行,可以在代码中添加说明文字,如: ```lingo ! 集部分; sets: ...

    多层板PCB设计参考

    例如,在双面板设计中,设计师可以参考文档中列举的不同厚度和材料组合,这些结构通常以诸如“50/100 || 0.5mm”这样的形式表达,表示铜箔厚度为50微米和100微米,以及层与层之间的介质厚度为0.5毫米。在实际设计中...

    2021年威海地区陆路运输主管岗位薪酬水平报告-最新数据.pdf

    报告中罗列的数字和百分比,涵盖了从P25到P90的薪资百分位数,以及中位数和不同所有制类型企业的薪酬数据。我们了解到,威海地区陆路运输主管的薪酬水平在不同企业类型中存在差异,包括外商独资企业、合资企业、当地...

    西门子_NRAQ.E75310 Programmable Controllers.pdf

    ADM模块集成了模拟和数字信号的处理,以更高效地解决工业自动化中的复杂问题。机器人控制器(CHASU-N)则是用于机器人的运动控制,确保机器人的精确操作和运动协调。 输入输出模块(I/O Modules)用于连接和处理...

    固高GTS系列运动控制卡编程手册

    1. **指令列表**:罗列了所有可用的指令,便于用户快速查找和参考。 2. **运动控制器函数库的使用**:包括了在不同开发环境下的使用指南,如Visual C++、Visual Basic、Delphi等。 3. **指令返回值及其意义**:解释...

    单片机应用举例.pdf

    由于提供的【部分内容】中包含了大量无法识别的乱码和字母数字组合,这使得直接理解文件内容变得异常困难。然而,我们还是可以从标题和描述中提取出关键信息:“单片机应用举例.pdf”,并且使用标签“技术”进行分类...

    颜色代码表

    每个分量的强度由两位十六进制数字表示,范围从00到FF,因此三个颜色分量组合起来共有六位数字。例如,#FF0000代表纯红色,而#00FF00代表纯绿色。 HTML颜色代码表罗列了一系列这样的十六进制值,涵盖了几乎所有的...

    2021年太原地区信用控制员岗位薪酬水平报告-最新数据.pdf

    报告中还包含了职业代码,这有助于快速索引到特定行业或岗位的薪酬数据,但是由于内容中也存在一些数字和字母组合,可能需要根据上下文进一步核实职业代码所代表的确切含义。 综上所述,这份报告是人力资源管理、...

    2021年四川省地区培训主管岗位薪酬水平报告-最新数据.pdf

    报告最后提到了本次薪酬调研岗位列表,显示了调研覆盖的岗位范围之广,并通过特定的字母和数字组合(如001X)来代表不同的职位和信息。这为希望了解不同岗位薪酬分布的读者提供了直接的参考。 整体来看,该薪酬水平...

Global site tag (gtag.js) - Google Analytics