我无能为力地试图解决这个问题:
Let
arr
be an array of integers of lengthn
(indexed from 1 to n).Let
M[s][i]
be a matrix containing boolean values of, if there exist a subset of firsti
numbers of the array arr (arr[1], arr[2], ..., arr[i], ..., arr[n]), of which the sum is exactlys
.Find the recursive formula for the value of
M[s][i]
based onM[?][j]
, where j < i andarr
containsj
. You can assume thatM[s][0] = 0
.
如何找到这个公式?如果有任何帮助,我将不胜感激。
最佳答案
基于您的 M[s][i]
定义的简单递归公式为:
M[s][i] = M[s][i-1] || M[s-arr[i]][i-1]
说明
- 如果
arr[i]
不包含在子集中,则M[s][i]
为true
如果 存在第一个i-1
元素的子集,其总和为 完全等于s
。 - 如果
arr[i]
包含在子集中,则M[s][i]
仅当存在第一个的子集时才为true
i - 1
个元素,其子集完全等于s - arr[i]
。
这个问题通常被称为子集和问题。它已经有多个答案 here
关于java - 动态规划——求公式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55871544/