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");
}
}
分享到:
相关推荐
当存在特定的限制条件时,如例题4中的数字之和必须大于8,我们需要在罗列过程中注意这些条件,按一定的顺序进行,避免重复和遗漏。 5. **循环赛问题**: 例题5讨论的是循环赛的场次计算。在循环赛中,每个队伍都...
= 3×2×1=6种排列),以及使用特定数字组成的两位数或三位数问题。 在学习过程中,学生需要培养观察、分析和推理的能力,养成有序思考的习惯。同时,掌握排列与组合的逻辑推理是学习难点,需要通过实践和讨论来...
在准备数字电子技术(数电)的期末复习时,我们需要关注多个关键知识点和例题,以便有效备考。以下是对这些内容的详细解析: 一、数选器与奇偶校验电路设计 4选1数选器74LS153可以用于实现奇偶校验电路。奇偶校验...
例如,例题1中要求在图形中填入数字,使得每边7个小三角形内数字之和相等,并求最大和。我们可以通过观察和分析,将最小的数填在中心位置,最大的数填在角上,以此类推,逐步构建出满足条件的最大和。 例题2中涉及...
- **设计简单的数字电路**:通过已知逻辑函数式,可以设计出对应的逻辑电路,实现特定的逻辑运算功能。 - **数字系统分析**:在分析数字系统时,能够将逻辑函数转换为真值表,进而分析系统的逻辑行为。 - **软件仿真...
- 在特定条件下,如例题3和训练题,需要考虑数字在不同位置上的组合,以满足等式和特定条件,如横行和竖行的和相等,或者数字的乘积相等。 5. **数字填充策略**: - 例题4中,通过分析0在加减乘法中的特殊角色,...
例如,“FP”代表某种型号的按钮开关,后续的字母和数字组合则标识着具体的尺寸、安装方式、电压等级和电气特性等。在工业自动化的开关选型中,以下几个关键知识点是非常重要的: 1. 开关类型:用户需要根据实际...
11. 题目61至65中出现了各种数字组合和字母,但无法从片段中明确判断具体的考察内容。 12. 题目67和68中出现了10EH和10DH,这些可能是十六进制数表示的数字,通常用在内存地址或某些寄存器的表示上。 13. 题目70至...
此外,文档中提到的一些符号和数字的组合,如“80%”、“24(911)”等,很可能是表示某种状态的百分比或与紧急事件相关的代码,例如与911相关的代码可能表示紧急状态或紧急服务的联系方式。而“P12Phoenix”、“P***%...
6. 计算数论:研究数字计算中的问题,特别是在大整数的因式分解、素数检验和计算模算术中,这在密码学和现代统计方法中尤其重要。 7. 组合数学:数论与组合数学有着密切的联系,组合设计和有限几何等领域都可能受益...
这里,`John`、`Jill`等是`students`集的成员,而`1`和`0`分别代表男性和女性,数字代表年龄。 ##### 3.3 注释 使用感叹号(!)开始的行被视为注释行,可以在代码中添加说明文字,如: ```lingo ! 集部分; sets: ...
例如,在双面板设计中,设计师可以参考文档中列举的不同厚度和材料组合,这些结构通常以诸如“50/100 || 0.5mm”这样的形式表达,表示铜箔厚度为50微米和100微米,以及层与层之间的介质厚度为0.5毫米。在实际设计中...
报告中罗列的数字和百分比,涵盖了从P25到P90的薪资百分位数,以及中位数和不同所有制类型企业的薪酬数据。我们了解到,威海地区陆路运输主管的薪酬水平在不同企业类型中存在差异,包括外商独资企业、合资企业、当地...
ADM模块集成了模拟和数字信号的处理,以更高效地解决工业自动化中的复杂问题。机器人控制器(CHASU-N)则是用于机器人的运动控制,确保机器人的精确操作和运动协调。 输入输出模块(I/O Modules)用于连接和处理...
1. **指令列表**:罗列了所有可用的指令,便于用户快速查找和参考。 2. **运动控制器函数库的使用**:包括了在不同开发环境下的使用指南,如Visual C++、Visual Basic、Delphi等。 3. **指令返回值及其意义**:解释...
由于提供的【部分内容】中包含了大量无法识别的乱码和字母数字组合,这使得直接理解文件内容变得异常困难。然而,我们还是可以从标题和描述中提取出关键信息:“单片机应用举例.pdf”,并且使用标签“技术”进行分类...
每个分量的强度由两位十六进制数字表示,范围从00到FF,因此三个颜色分量组合起来共有六位数字。例如,#FF0000代表纯红色,而#00FF00代表纯绿色。 HTML颜色代码表罗列了一系列这样的十六进制值,涵盖了几乎所有的...
报告中还包含了职业代码,这有助于快速索引到特定行业或岗位的薪酬数据,但是由于内容中也存在一些数字和字母组合,可能需要根据上下文进一步核实职业代码所代表的确切含义。 综上所述,这份报告是人力资源管理、...
报告最后提到了本次薪酬调研岗位列表,显示了调研覆盖的岗位范围之广,并通过特定的字母和数字组合(如001X)来代表不同的职位和信息。这为希望了解不同岗位薪酬分布的读者提供了直接的参考。 整体来看,该薪酬水平...