动态规划与可变维度

huangapple go评论76阅读模式
英文:

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);
}

然后,您可以创建三个实际实现的子类:

  1. HigherMultiDimArray,其维度为2+。
  2. OneDimArray,其维度为1,实际存储数据的地方。
  3. ZeroDimArray,其维度为0,基本上是围绕一个int的包装器,存在是为了在需要时为OneDimArray提供返回值。

这将允许您声明任意维度的数组。

但是,您会发现,一个具有每个维度上有10个值的10维数组将包含100亿个元素,可能会导致内存耗尽。

因此,我建议您找到一个一维结构来回答以下问题:

  1. 我们需要获取到值 x 需要多少个值?
  2. 最后一个使我们达到目标值 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.

  1. A HigherMultiDimArray whose dimension is 2+.
  2. A OneDimArray whose dimension is 1, and is where data is actually stored.
  3. A ZeroDimArray whose dimension is 0, is basically a wrapper around an int, and which exists to give OneDimArray 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:

  1. How many values do we need to get to value x?
  2. 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!

huangapple
  • 本文由 发表于 2023年3月15日 18:05:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/75743196.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定