c++ - 使用每一行的二维数组中小于或等于 k ​​的最大可能总和

Question

给定:一个二维数组，值 K 和 M

问题:使用恰好 M 个元素，使用所有行(即每行应该有一个元素)找到小于或等于 K 的最大可能总和。

这是一个程序片段，我无法实现每一行和 M 的条件。

for (int i = 0 ; i<n ; i++)
    for (int s=0; s<M; s++)
        for (int j=K;j>=0;j--)
            if (dp[s][j] && A[i] + j < K)
                dp[s + 1][j + A[i]] = true;

编辑 1:Rows = M ，即必须从每一行中选择一个元素。

编辑 2:动态规划解决方案，感谢 @6502

ill ret(V(ill) col[101],ill prec[][101],ill s,ill row,ill m,ill k)
{
    if(prec[s][row])
    return prec[s][row];
    else
    {
        if(row==m+1)
        return s;
        ill best=-1;
        int j=row;

        for(int i=0;i<col[j].size();i++)
        {
            if(s+col[j][i] <= k)
            {
                ill x = ret (col,prec,s+col[j][i],row+1,m,k);
                if ((best==-1)||(x>best))
                best=x;

            }
        }
        prec[s][row]=best;
        return best;
    }


}

Answer 1

可以使用动态规划解决问题，方法是选择 (s, row) 对作为状态，其中 s 是当前总和，row 是我们需要包括的下一行。

最大原则是有效的，因为无论我们在前面的行中做出何种选择，结果仅取决于当前总和和当前行索引。

在代码中(Python)

cache = {}

data = [[2, 3, 4],
        [2, 3, 4],
        [2, 3, 4]]

M = 3
K = 10

def msum(s, row):
    try:
        return cache[s, row]
    except KeyError:
        if row == M:
            return s
        best = None
        for v in data[row]:
            if s+v <= K:
                x = msum(s+v, row+1)
                if best is None or x > best:
                    best = x
        cache[s, row] = best
        return best

print msum(0, 0)

如果不存在解决方案，该函数返回 None(即即使从每一行中取最小值，我们最终也会超过 K)。