Question

Use dynamic programming to find N nonnegative numbers, say x1, Xy, to maximize subject to the constraint = X, where is positive integer and is given nonnegative

number.​

Answer 1

Explanation:

Given a linear equation of n variables, find number of non-negative integer solutions of it. For example,let the given equation be “x + 2y = 5”, solutions of this equation are “x = 1, y = 2”, “x = 5, y = 0” and “x = 1. It may be assumed that all coefficients in given equation are positive integers.

Example :

Input: coeff[] = {1, 2}, rhs = 5

Output: 3

The equation "x + 2y = 5" has 3 solutions.

(x=3,y=1), (x=1,y=2), (x=5,y=0)

Input: coeff[] = {2, 2, 3}, rhs = 4

Output: 3

The equation "2x + 2y + 3z = 4" has 3 solutions.

(x=0,y=2,z=0), (x=2,y=0,z=0), (x=1,y=1,z=0)

We strongly recommend you to minimize your browser and try this yourself first.

We can solve this problem recursively. The idea is to subtract first coefficient from rhs and then recur for remaining value of rhs.

If rhs = 0

countSol(coeff, 0, rhs, n-1) = 1

Else

countSol(coeff, 0, rhs, n-1) = ∑countSol(coeff, i, rhs-coeff[i], m-1)

where coeff[i]<=rhs and

i varies from 0 to n-1

Below is recursive implementation of above solution.

// A naive recursive C++ program to

// find number of non-negative solutions

// for a given linear equation

#include<bits/stdc++.h>

using namespace std;

// Recursive function that returns

// count of solutions for given rhs

// value and coefficients coeff[start..end]

int countSol(int coeff[], int start,

int end, int rhs)

{

// Base case

if (rhs == 0)

return 1;

// Initialize count

// of solutions

int result = 0;

// One by subtract all smaller or

// equal coefficiants and recur

for (int i = start; i <= end; i++)

if (coeff[i] <= rhs)

result += countSol(coeff, i, end,

rhs - coeff[i]);

return result;

}

// Driver Code

int main()

{

int coeff[] = {2, 2, 5};

int rhs = 4;

int n = sizeof(coeff) / sizeof(coeff[0]);

cout << countSol(coeff, 0, n - 1, rhs);

return 0;

}