英文:
Dynamic Programming with variable dimensions
问题
给定一组唯一的基本整数和一个目标值,返回使基本整数相加等于目标值的组合。返回的组合必须包含最少数量的元素。
例如1:
给定:baseIntegers = [4, 7]; target = 15;
返回:[7, 4, 4]
解释:7+4+4=15。
例如2:
给定:baseIntegers = [3, 5, 7]; target = 18;
返回:[7, 5, 3, 3]
解释:7+5+3+3=18。没有返回[3, 3, 3, 3, 3],因为它比[7, 5, 3, 3]多了1个元素。
例如3:
给定:baseIntegers = [5, 6, 8, 11]; target = 52;
返回:[11, 11, 11, 11, 8]
解释:11+11+11+11+8=52。
例如4:
给定:baseIntegers = [2, 5]; target = 3;
返回:[]
解释:2和5不能相加得到3。
对于解决这个问题,你可以考虑使用Java编程语言以及动态规划的方法。你可以根据目标值和基本整数的集合动态构建一个二维数组,以存储可能的和的组合。然后,你可以回溯这个数组来找到达到目标值的组合。
但是,问题在于如何处理未知长度的baseIntegers。你可以使用动态规划的方法,但需要在程序中动态调整数组的大小以适应不同长度的输入。这需要一些额外的编程工作,但是是可行的。
英文:
Resently I encountered this problem:
Given a set of unique base integers and a target value, return the combination of base integers which add up to the target value. The returned combination has to have the least amount of elements.
Example 1.
Given: baseIntegers = [4, 7]; target = 15;
Return: [7, 4, 4]
Explanation: 7+4+4=15.
Example 2.
Given: baseIntegers = [3, 5, 7]; target = 18;
Return: [7, 5, 3, 3]
Explanation: 7+5+3+3=18. [3, 3, 3, 3, 3] is not returned since it contains 1 more element than [7, 5, 3, 3]
Example 3.
Given: baseIntegers = [5, 6, 8, 11]; target = 52;
Return: [11, 11, 11, 11, 8]
Explanation: 11+11+11+11+8=52.
Example 4.
Given: baseIntegers = [2, 5]; target = 3;
Return: []
Explanation: 2,5 do not add up to 3.
For example 1, I came up with an approach to solve the question using Dynamic Programming.
Without going into much details, I created a 2-dimentional array to store the sum of the base integers:
sum[0,0] = 0
sum[1,0] = sum[0,0]+4 = 4
sum[1,1] = sum[1,0]+7 = 11
sum[2,1] = sum[1,1]+4 = 15
...
When I found the target sum, I retrieve the result from the dimensions [2,1] (2 fours and 1 seven).
I can do example 3 in similar fashion by creating a 4-dimentional array.
However, I'm stuck if I need to solve the problem without knowing the length of baseIntegers ahead of time.
The reason is that I can not create a multi-dimensional array without knowing its dimension beforehand.
So here is my problem: Is there any way to solve this problem with variable input length?
Preferablly with java, thanks!
答案1
得分: 2
首先,如果您想创建一个可变维度的数组,您可以简单地创建一个接口。类似于这样:
public interface MultiDimArray {
int dim;
int get(int[] idx);
void set(int[] idx, int value);
MultiDimArray getAll(int[] partialIdx);
void setAll(int[] partialIdx, MultiDimArray values);
}
然后,您可以创建三个实际实现的子类:
HigherMultiDimArray
,其维度为2+。OneDimArray
,其维度为1,实际存储数据的地方。ZeroDimArray
,其维度为0,基本上是围绕一个int
的包装器,存在是为了在需要时为OneDimArray
提供返回值。
这将允许您声明任意维度的数组。
但是,您会发现,一个具有每个维度上有10个值的10维数组将包含100亿个元素,可能会导致内存耗尽。
因此,我建议您找到一个一维结构来回答以下问题:
- 我们需要获取到值
x
需要多少个值? - 最后一个使我们达到目标值
x
的值是什么?
现在,您处理的数据量是可以管理的。使用“动态规划”来找出如何实现这一点并不难。
如果您聪明地使用A*搜索算法,甚至可以让这一过程更加快速。
英文:
First of all if you want to create a variable dimension array, you can simply create an interface. Something like this.
public interface MultiDimArray {
int dim;
int get (int[] idx);
void set (int[] idx, int value);
MultiDimArray getAll (int[] partialIdx);
void setAll(int[] partialIdx, MultiDimArray values);
}
Then you create three subclasses that can be actually implemented.
- A
HigherMultiDimArray
whose dimension is 2+. - A
OneDimArray
whose dimension is 1, and is where data is actually stored. - A
ZeroDimArray
whose dimension is 0, is basically a wrapper around anint
, and which exists to giveOneDimArray
something to return at need.
This will let you declare an array of any dimension.
BUT you will find that a 10-dimensional array with 10 values per dimension takes 10 billion elements and you'll run out of memory.
Therefore I would recommend that you find a one dimensional structure to answer the questions:
- How many values do we need to get to value
x
? - What is a last value that got us there?
And now you're dealing with a manageable amount of data. It isn't hard to use "dynamic programming" to figure out how to get this reasonably.
If you are clever about using something called A* Search, you can make getting this even faster.
答案2
得分: 0
你考虑过循环吗?类似这样的方式:
i = 1
j = 1
for value in len(baseIntegers):
sum[i, j] = sum[i-1, j-1]
不确定这种方法的扩展性如何,但我在Python中迅速尝试过,它有效!
英文:
Have you considered loops? So something like:
i = 1
j = 1
for value in len(baseIntegers):
sum[i,j] = sum[i-1,j-1]
Unsure how well this would scale but I did it quickly in Python and it worked!
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论