CODEWITHSUNDEEP
c++algorithmdynamic-programming
shubhamr
shubhamr

Reputation: 465

Maximum possible sum less than or equal to k in a 2D array using each row

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;
    }


}

Upvotes: 3

Views: 1581

Answers (3)

6502
6502

Reputation: 114481

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).

Upvotes: 1

imswapy
imswapy

Reputation: 132

This can be solved using boolean 2D table. The value of dp[r][s] is set to true, if its possible to generate sum 's' , using exactly 'r' rows (i.e exactly one element from each of the [0 to r-1] rows). Using this dp table, we can compute next state as 

              dp[r+1][s] |= dp[r][s-A[r+1][c]]  ; 0 < c < N, 0 < s <= K

where N is number of columns(0-based indexing). Finally return the value of max index set in M-1 row of dp table

Following is a bottom-up implementation

// Assuming input matrix is M*N
int maxSum() {
    memset(dp, false, sizeof(dp));

    //Initialise base row
    for (int c = 0; c < N; ++c)
        dp[0][A[0][c]] = true;

    for ( int r = 1; r < M; ++r ) {
        for ( int c = 0; c < N; ++c) {
            // For each A[r][c], check for all possible values of sum upto K
            for (int sum = 0; sum <= K; ++sum) {
                if ( sum-A[r][c] >= 0 && dp[r-1][sum-A[r][c]] )
                    dp[r][sum] = true;
            }
        }
    }

    // Return max possible value <= K
    for (int sum = K; sum >= 0; --sum) {
        if ( dp[M-1][sum] )
            return sum;
    }

    return 0;
}

Note that dp table values for current row depend only on previous row, as such space optimization trick can be used to solve it using 1-D table

Upvotes: 1

Jarod42
Jarod42

Reputation: 217275

A brute force approach:

bool increase(const std::vector<std::vector<int>>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] > v[index].size()) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

int sum(const std::vector<std::vector<int>>& v, const std::vector<std::size_t>& it)
{
    int res = 0;
    for (std::size_t i = 0; i != it.size(); ++i) {
        res += v[i][it[i]];
    }
    return res;
}

int maximum_sum_less_or_equal_to_K(const std::vector<std::vector<int>>& v, int K)
{
    std::vector<std::size_t> it(v.size());
    int res = K + 1;

    do {
        int current_sum = sum(v, it);
        if (current_sum <= K) {
            if (res == K + 1 || res < current_sum) {
                res = current_sum;
            }
        }
    } while (increase(v, it));
    if (res == K + 1) {
        // Handle no solution
    }
    return res;
}

it has the current selection of each row.

Upvotes: 1

Related Questions