Integer Partitioning Problem


Python

Python : Integer partitioning algorithm using dynamic programming implemented in Python3


C++ : Integer partitioning algorithm with dynamic programming implemented in C++11

#include<iostream>
#include<vector>

using namespace std;

int GetPartitions(vector<int>& numset, int biggernum) {

    int size_numset = numset.size();
    int dptable[size_numset+1][biggernum+1];

    // Number 0 can be obtained with 0 smaller numbers i.e 1 way
    dptable[0][0] = 1;

    // Numbers greater that 0 cannot be obtained with number 0
    for (int n=1; n<=biggernum; n++) {
        dptable[0][n] = 0;
    }

    // Number 0 can be obtained with any number i.e we do not include any number from the set
    for (int r=1; r<=size_numset; r++) {
        dptable[r][0] = 1;
    }

    for (int r=1; r<=size_numset; r++) {
        for (int c=1; c<=biggernum; c++) {
            if (c >= numset[r-1]) {
               // Exclude the last number in the numset + Include last number in the numset
               dptable[r][c] = dptable[r-1][c] + dptable[r][c-numset[r-1]];
            } else {
               // Exclude the last number in the numset as it is bigger in value
               dptable[r][c] = dptable[r-1][c];
            }
        }
    }

    return dptable[size_numset][biggernum];
}

int main() {

    int num = 4;
    vector<int> set_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */
    cout << GetPartitions(set_1, num) << endl;

    num = 6;
    vector<int> set_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */
    cout << GetPartitions(set_2, num) << endl;

    num = 10;
    vector<int> set_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */
    cout << GetPartitions(set_3, num) << endl;

    return 0;
}

Output

4
3
4

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.