找到一个解决方案使用动态编程子集和 [英] find a solution to subset sum using dynamic programming

问题描述

我想做什么

我想找到一个数组中，总结到目标 T 的一个子集。我也想用一个动态规划方法（和一个自下而上的解决方案）来做到这一点。

I want to find a subset of an array that sums to a target T. I also want to use to a dynamic programming approach (and a bottom-up solution at that) to do this.

我现在有什么

目前我只发现了一种方法，如果看到大小之间的所有子集 N ，无论是否存在至少一个子集，它具有所需的总和。见下面code。

Currently I only found a way to see if amongst all subsets of size N, whether or not there is at least one subset that has the desired sum. See code below.

public boolean solve(int[] numbers, int target) {

    //Safeguard against invalid parameters
    if ((target < 0) || (sum(numbers) < target)){
        return false;
    }

    boolean [][] table = new boolean [target + 1] [numbers.length + 1]  ;

    for (int i = 0; i <= numbers.length; ++i) {
        table[0][i] = true;
    }


    /* Base cases have been covered. 
     * Now look set subsets [1..n][target] to be true or false.
     * n represents the number of elements from the start that have a subset 
     * that sums to target
     */
    for (int i = 1; i <= target; ++i){
        for (int j = 1; j <= numbers.length; ++j){
            /* Mark index j as one of the numbers in the array
             *  which is part of the solution with the given subtarget */
            table [i][j] = table[i][j-1];
            if (i >= numbers[j-1])
                table[i][j] = table[i][j] || table[i - numbers[j-1]] [j-1];
        }
    }

    return table[target][numbers.length];
}

我在哪里卡住

现在，我知道，如果有的是的一个解决方案，但我不能想办法到实际输出的解决方案。

Right now, I know if there is a solution, but I can't think of a way to actually output a solution.

我不想找任何人给我提供具体code，但伪code是值得欢迎的提示，如何解决可能会被保存。

I am not looking for anyone to provide me specific code, but pseudocode is welcome as are hints to how a solution may be saved.

推荐答案

您提供可以保持相同的算法，你并不需要存储除了DP-表别的 TABLE [] [ ] 。你只需要在你一步倒退通过一个额外的后处理阶段 TABLE [] [] 获得的解集。

The algorithm you provided can stay the same, you don't need to store anything else besides the DP-table table[][]. You just need an additional post-processing phase in which you step "backwards" through table[][] to get the solution set.

只是为了回忆：

您已经计算表表[I] [J] ，它存储了每个值0℃= I＆LT; = T（：= 目标），每一个0℃= J＆LT; = N（：= numbers.length ）是否有数字的一个子集号[0..j-1] 的总和我。

You've computed the table table[i][j], which stores for every value 0<=i<=t(:=target) and every 0<=j<=n(:=numbers.length) whether there is a subset of numbers in numbers[0..j-1] that sum to i.

考虑子集S对应表[I] [J] （，这是真的）。注意：

• 该子集S包含数字号码[J] 仅表[i编号[J] [J-1] 是真实的。

  Consider the subset S corresponding to table[i][j] (, which is true). Note that:

  • The subset S contains the number numbers[j] only if table[ i-numbers[j] ][j-1] is true.

    （证明：递归取溶液的子集S'为表[i编号[J] [J-1] ，并添加号码[J] ）

  • 在另一方面，该子集S不包含数字号码[J] 仅表[i编号[J] [J- 1] 是假的。

    (Proof: recursively take the solution subset S' for table[ i-numbers[j] ][j-1], and add numbers[j])

  • On the other hand, this subset S does not contain the number numbers[j] only if table[ i-numbers[j] ][j-1] is false.

    （证明：假设S包含号码[J] ，特罗号码[J] 输出S，这意味着表[i编号[J] [J-1] ，矛盾）

  (Proof: assume S contains numbers[j], trow numbers[j] out of S, this implies table[ i-numbers[j] ][j-1], contradiction)

  • 如果是这样，递归计算是否号码[N-2] 是集总结与T - 号码[N-1] ，
  • 否则递归计算是否号码[N-2] ，是在集总结到t
  • If so, recursively compute whether numbers[n-2] is in the subset summing to t-numbers[n-1],
  • else recursively compute whether numbers[n-2], is in the subset summing to t

  这篇关于找到一个解决方案使用动态编程子集和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！