Given : A two dimensional array , values K and M
Problem : Find the maximum possible sum less than or equal K using all the rows (i.e there should be an element form each row) using exactly M elements.
This is a snippet of a program, I am having trouble implementing the conditions for each row and 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;
EDIT 1: Rows = M , i.e one element from each row has to be selected.
EDIT 2 : Dynamic Programming Solution, Thanks to @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;
}
}
The problem can be solved using dynamic programming by choosing as state the pair (s, row) where s is the current sum and row is the next row we need to include.
The maximal principle is valid because no matter on which choices we made in previous rows the result depends only on the current sum and the current row index.
In code (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)
The function returns None if no solution exists (i.e. if even taking the smallest value from each row we end up exceeding K).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments