我正在尝试解决数字问题:
我收到一个数字，必须计算加起来才能得到该数字的数字，有些规则使它变得更难
规则:
- 只能是正数，总和不能包含0
- 总和只能由6个数字组成，不能多也不能少
- 要添加的数字可以从 1 到 45
- 不能重复数字
- 最大金额为255
- 最低金额为 21
- 一个有效的组合是 1、2、3、4、5、6，就像 6、5、4、3、2、1 或 3、4、5、1、6、2，但只算作一个组合，因为包含相同的数字但顺序不同
我一直在尝试像在背包问题中那样做，但不同的是我必须选择固定数量的数字来求和。
如果有人有解决此问题的算法想法，我将不胜感激。
最佳答案
你可以使用动态规划来解决这个问题。
图 dp[N][LastNumber][ElementCount] 有多少种方式产生 N 最后一个数字是 LastNumber 和元素的数量是ElementCount。 N = 1..255，LastNumber = 1..45，ElementCount = 1..6
您可以从子解决方案中获取 dp[N][LastNumber][ElementCount]
dp[N-LastNumber][1][ElementCount-1] + dp[N-LastNumber][2][ElementCount-1] ... + dp[N-LastNumber][LastNumber-1][ElementCount-1]
基本情况是 dp[i][i][1] = 1 for i = 1..45
如果问有多少种方式求和M，答案是dp[M][i][6] for i = 1。 .45
关于java - 获取所有可能的组合以获得给定的没有重复数字的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39969534/