找到一个解决方案使用动态编程子集和

编程入门行业动态更新时间:2024-10-26 19:33:26

本文介绍了找到一个解决方案使用动态编程子集和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

我想做什么

我想找到一个数组中，总结到目标 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] ，矛盾）