算法练习 -- DP 查找和为指定数字的数组
问题：
从2,4,3,5,7,1,9,10中找出多个数，和为11
这个题目是0 1背包的一个变体，因此可用DP来解。
DP解法的关键在于得到递推公式，对于这个问题来说，DP公式为：
j ∈[1,11]
i ∈[0,7]
dp[i][j] = 从(arr[i], dpArr[i-1][j], arr[i] + dpArr[i-1][j], arr[i]+ dpArr[i-1][j-arr[i]]) 中选出小于j的最大值
具体代码如下：
void Main()
{
DpFind();
Console.WriteLine(dpArr);
}
static int n = 11;
static int[] arr = new int[]{2,4,3,5,7,9,10,6};
static int[,] dpArr = new int[8,12];
//j = 1..n , loop each element in arr
//dpArr[i,j] = Max(arr[i], dpArr[i-1][j], arr[i] + dpArr[i-1][j], arr[i]+ dpArr[i-1][j-arr[i]]) and the max not gather than j
static void DpFind(){
for(var i = 0; i < arr.Length; i++){
for(var j = 1; j <= n; j++){
if(i == 0){
var max = arr[i] > j ? 0 : arr[i];
dpArr[i,j] = max;
results[i+","+j] = max;
}
else if(i > 0){
var maxArr = new List<int>(){arr[i], dpArr[i-1,j],arr[i] + dpArr[i-1,j]};
if(j > arr[i]){
maxArr.Add(arr[i] + dpArr[i-1,j-arr[i]]);
}
dpArr[i,j] = MaxLessThan(j,maxArr.ToArray());
}
}
}
}
//find the max element in arr when less than x
static int MaxLessThan(int x , params int[] arr){
int s = 0;
for(var i = 0;i < arr.Length; i++){
if(arr[i] > s && arr[i] <= x){
s = arr[i];
}
}
return s;
}DP中最后1个元素即dpArr[7][11]就是问题的解