# include # include # include # include # include "subset_sum.h" /******************************************************************************/ int i4_max ( int i1, int i2 ) /******************************************************************************/ /* Purpose: i4_max() returns the maximum of two I4's. Licensing: This code is distributed under the MIT license. Modified: 29 August 2006 Author: John Burkardt Input: int I1, I2, are two integers to be compared. Output: int I4_MAX, the larger of I1 and I2. */ { int value; if ( i2 < i1 ) { value = i1; } else { value = i2; } return value; } /******************************************************************************/ int i4_min ( int i1, int i2 ) /******************************************************************************/ /* Purpose: i4_min() returns the smaller of two I4's. Licensing: This code is distributed under the MIT license. Modified: 29 August 2006 Author: John Burkardt Input: int I1, I2, two integers to be compared. Output: int I4_MIN, the smaller of I1 and I2. */ { int value; if ( i1 < i2 ) { value = i1; } else { value = i2; } return value; } /******************************************************************************/ int i4_power ( int i, int j ) /******************************************************************************/ /* Purpose: i4_power() returns the value of I^J. Licensing: This code is distributed under the MIT license. Modified: 23 October 2007 Author: John Burkardt Input: int I, J, the base and the power. J should be nonnegative. Output: int I4_POWER, the value of I^J. */ { int k; int value; if ( j < 0 ) { if ( i == 1 ) { value = 1; } else if ( i == 0 ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "I4_POWER - Fatal error!\n" ); fprintf ( stderr, " I^J requested, with I = 0 and J negative.\n" ); exit ( 1 ); } else { value = 0; } } else if ( j == 0 ) { if ( i == 0 ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "I4_POWER - Fatal error!\n" ); fprintf ( stderr, " I^J requested, with I = 0 and J = 0.\n" ); exit ( 1 ); } else { value = 1; } } else if ( j == 1 ) { value = i; } else { value = 1; for ( k = 1; k <= j; k++ ) { value = value * i; } } return value; } /******************************************************************************/ int *i4_to_digits_binary ( int i, int n ) /******************************************************************************/ /* Purpose: i4_to_digits_binary() produces the binary digits of an I4. Example: I N C Binary -- --- --- ------------ 0 1 0 0 0 2 0, 0 00 1 3 1, 0, 0 100 2 3 0, 1, 0 010 3 3 1, 1, 0 011 4 3 0, 0, 1 100 8 3 0, 0, 0 (1)000 8 5 0, 0, 0, 1, 0 01000 -8 5 0, 0, 0, 1, 0 (-) 01000 0 3 0, 0, 0 1 3 1, 0, 0 2 3 0, 1, 0 3 3 1, 1, 0 4 3 0, 0, 1 5 3 1, 0, 1 6 3 0, 1, 1 7 3 1, 1, 1 Licensing: This code is distributed under the MIT license. Modified: 19 December 2011 Author: John Burkardt Input: int I, the integer to be analyzed. int N, the number of digits to determine. Output: int I4_TO_DIGITS_BINARY[N], the first N binary digits of I. Entry 0 is the units digit. */ { int *c; int j; c = ( int * ) malloc ( n * sizeof ( int ) ); i = abs ( i ); for ( j = 0; j < n; j++ ) { c[j] = i % 2; i = ( i - c[j] ) / 2; } return c; } /******************************************************************************/ int *i4vec_copy_new ( int n, int a1[] ) /******************************************************************************/ /* Purpose: i4vec_copy_new() copies an I4VEC. Discussion: An I4VEC is a vector of I4's. Licensing: This code is distributed under the MIT license. Modified: 04 July 2008 Author: John Burkardt Input: int N, the number of entries in the vectors. int A1[N], the vector to be copied. Output: int I4VEC_COPY_NEW[N], the copy of A1. */ { int *a2; int i; a2 = ( int * ) malloc ( n * sizeof ( int ) ); for ( i = 0; i < n; i++ ) { a2[i] = a1[i]; } return a2; } /******************************************************************************/ int i4vec_dot_product ( int n, int x[], int y[] ) /******************************************************************************/ /* Purpose: i4vec_dot_product() computes the dot product of two I4VEC's. Discussion: An I4VEC is a vector of I4's. Licensing: This code is distributed under the MIT license. Modified: 19 December 2011 Author: John Burkardt Input: int N, the size of the array. int X[N], Y[N], the arrays. Output: int I4VEC_DOT_PRODUCT, the dot product of X and Y. */ { int i; int value; value = 0; for ( i = 0; i < n; i++ ) { value = value + x[i] * y[i]; } return value; } /******************************************************************************/ void i4vec_print ( int n, int a[], char *title ) /******************************************************************************/ /* Purpose: i4vec_print() prints an I4VEC. Discussion: An I4VEC is a vector of I4's. Licensing: This code is distributed under the MIT license. Modified: 14 November 2003 Author: John Burkardt Input: int N, the number of components of the vector. int A[N], the vector to be printed. char *TITLE, a title. */ { int i; fprintf ( stdout, "\n" ); fprintf ( stdout, "%s\n", title ); fprintf ( stdout, "\n" ); for ( i = 0; i < n; i++ ) { fprintf ( stdout, " %6d: %8d\n", i, a[i] ); } return; } /******************************************************************************/ int subset_sum_count ( int n, int w[], int t, int ind_min, int ind_max ) /******************************************************************************/ /* Purpose: subset_sum_count() counts solutions to the subset sum problem in a range. Licensing: This code is distributed under the MIT license. Modified: 02 February 2012 Author: John Burkardt Input: int N, the size of the subset. int W[N], a set of weights. The length of this array must be no more than 31. int T, the target value. int IND_MIN, IND_MAX, the lower and upper limits to be searched. 0 <= IND_MIN <= IND_MAX <= (2^N)-1. Output: int SUBSET_SUM_COUNT, the number of distinct solutions of the subset sum problem found within the given range. */ { int *c; int ind; int ind_max2; int ind_min2; int solution_num; /* Check the data. */ if ( n < 1 ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "SUBSET_SUM_COUNT - Fatal error!\n" ); fprintf ( stderr, " N < 1.\n" ); exit ( 1 ); } if ( 31 < n ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "SUBSET_SUM_COUNT - Fatal error!\n" ); fprintf ( stderr, " 31 < N.\n" ); exit ( 1 ); } ind_min2 = i4_max ( ind_min, 0 ); ind_max2 = i4_min ( ind_max, i4_power ( 2, n ) - 1 ); /* Run through the range. */ printf ( "\n" ); printf ( " Searching from IND_MIN = %d", ind_min2 ); printf ( " through IND_MAX = %d\n", ind_max2 ); solution_num = 0; for ( ind = ind_min2; ind <= ind_max2; ind++ ) { /* Convert INDEX into vector of indices in W. */ c = i4_to_digits_binary ( ind, n ); /* If the sum of those weights matches the target, return combination. */ if ( i4vec_dot_product ( n, c, w ) == t ) { solution_num = solution_num + 1; } free ( c ); } return solution_num; } /******************************************************************************/ void subset_sum_count_test ( int n, int w[], int t, int ind_min, int ind_max ) /******************************************************************************/ /* Purpose: subset_sum_count_test() tests subset_sum_count(). Licensing: This code is distributed under the MIT license. Modified: 10 November 2015 Author: John Burkardt Input: int N, the number of weights. int W[N], a set of weights. The length of this array must be no more than 31. int T, the target value. int IND_MIN, IND_MAX, the lower and upper limits to be searched. */ { int solution_num; printf ( "\n" ); printf ( "SUBSET_SUM_COUNT_TESTS:\n" ); printf ( " SUBSET_SUM_COUNT_TEST calls SUBSET_SUM_COUNT with\n" ); printf ( " a particular set of problem data.\n" ); printf ( "\n" ); printf ( " Target value T = %d\n", t ); i4vec_print ( n, w, " Weight vector W:" ); solution_num = subset_sum_count ( n, w, t, ind_min, ind_max ); printf ( "\n" ); printf ( " Number of solutions = %d\n", solution_num ); return; } /******************************************************************************/ void subset_sum_count_tests ( ) /******************************************************************************/ /* Purpose: subset_sum_count_tests() tests subset_sum_count_test(). Licensing: This code is distributed under the MIT license. Modified: 10 November 2015 Author: John Burkardt */ { int ind_max; int ind_min; int n; int t; int test; int test_num = 9; int *w; static int w01[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w02[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w03[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w04[10] = { 267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922 }; static int w05[21] = {518533, 1037066, 2074132, 1648264, 796528, 1593056, 686112, 1372224, 244448, 488896, 977792, 1955584, 1411168, 322336, 644672, 1289344, 78688, 157376, 314752, 629504, 1259008}; static int w06[10] = { 41, 34, 21, 20, 8, 7, 7, 4, 3, 3 }; static int w07[9] = { 81, 80, 43, 40, 30, 26, 12, 11, 9 }; static int w08[6] = { 1, 2, 4, 8, 16, 32 }; static int w09[10] = { 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 }; printf ( "\n" ); printf ( "subset_sum_count_tests():\n" ); printf ( " subset_sum_count_test() calls SUBSET_SUM_COUNT with\n" ); printf ( " a particular set of problem data.\n" ); for ( test = 1; test <= test_num; test++ ) { if ( test == 1 ) { n = 8; w = i4vec_copy_new ( n, w01 ); t = 53; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 2 ) { n = 8; w = i4vec_copy_new ( n, w02 ); t = 53; ind_min = 68; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 3 ) { n = 8; w = i4vec_copy_new ( n, w03 ); t = 53; ind_min = 167; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 4 ) { n = 10; w = i4vec_copy_new ( n, w04 ); t = 5842; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 5 ) { n = 21; w = i4vec_copy_new ( n, w05 ); t = 2463098; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 6 ) { n = 10; w = i4vec_copy_new ( n, w06 ); t = 50; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 7 ) { n = 9; w = i4vec_copy_new ( n, w07 ); t = 100; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 8 ) { n = 6; w = i4vec_copy_new ( n, w08 ); t = 22; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 9 ) { n = 10; w = i4vec_copy_new ( n, w09 ); t = 50; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } subset_sum_count_test ( n, w, t, ind_min, ind_max ); free ( w ); } return; } /******************************************************************************/ int *subset_sum_find ( int n, int w[], int t, int ind_min, int ind_max, int *ind ) /******************************************************************************/ /* Purpose: subset_sum_find() seeks a subset of a set that has a given sum. Discussion: This function tries to compute a target value as the sum of a selected subset of a given set of weights. This function works by brute force, that is, it tries every possible subset to see if it sums to the desired value. Given N weights, every possible selection can be described by one of the N-digit binary numbers from 0 to 2^N-1. This function includes a range, which allows the user to control which subsets are to be checked. Thus, if there are N weights, specifying a range of [ 0, 2^N-1] indicates that all subsets should be checked. On the other hand, this full range could be broken down into smaller subranges, each of which could be checked independently. It is possible that, in the given range, there may be multiple solutions of the problem. This function will only return one such solution, if found. However, the function may be called again, with an appropriate restriction of the range, to continue the search for other solutions. Example: w = [ 1, 2, 4, 8, 16, 32 ]; t = 22; ind_min = 0 ind_max = 2^6 - 1 call subset_sum ( w, t, ind_min, ind_max, c, ind ) c = [ 2, 3, 5 ] ind = 22 Licensing: This code is distributed under the MIT license. Modified: 02 February 2012 Author: John Burkardt Input: int N, the size of the subset. int W[N], a set of weights. The length of this array must be no more than 31. int T, the target value. int IND_MIN, IND_MAX, the lower and upper limits to be searched. 0 <= IND_MIN <= IND_MAX <= (2^N)-1. Output: int *IND, the index of the solution. If IND is -1, no solution was found in the range. int SUBSET_SUM_FIND[N], indicates the solution, assuming that IND is not -1. In that case, the sum T is made by selecting those weights W(I) for which C(I) is 1. In fact, T = sum ( 1 <= I <= N ) C(I) * W(I). */ { int *c; int ind_max2; int ind_min2; /* Check the data. */ if ( n < 1 ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "SUBSET_SUM_FIND - Fatal error!\n" ); fprintf ( stderr, " N < 1.\n" ); exit ( 1 ); } if ( 31 < n ) { fprintf ( stderr, "\n" ); fprintf ( stderr, "SUBSET_SUM_FIND - Fatal error!\n" ); fprintf ( stderr, " 31 < N.\n" ); exit ( 1 ); } ind_min2 = i4_max ( ind_min, 0 ); ind_max2 = i4_min ( ind_max, i4_power ( 2, n ) - 1 ); /* Run through the range. */ printf ( "\n" ); printf ( " Searching from IND_MIN = %d", ind_min2 ); printf ( " through IND_MAX = %d\n", ind_max2 ); for ( *ind = ind_min2; *ind <= ind_max2; (*ind)++ ) { /* Convert INDEX into vector of indices in W. */ c = i4_to_digits_binary ( *ind, n ); /* If the sum of those weights matches the target, return combination. */ if ( i4vec_dot_product ( n, c, w ) == t ) { return c; } free ( c ); } *ind = - 1; return NULL; } /******************************************************************************/ int subset_sum_find_test ( int n, int w[], int t, int ind_min, int ind_max ) /******************************************************************************/ /* Purpose: subset_sum_find_test() tests subset_sum_find(). Licensing: This code is distributed under the MIT license. Modified: 10 November 2015 Author: John Burkardt Input: int N, the number of weights. int W[N], a set of weights. The length of this array must be no more than 31. int T, the target value. int IND_MIN, IND_MAX, the lower and upper limits to be searched. Output: int SUBSET_SUM_FIND_TEST, the index of a solution, if found, or the value -1 otherwise. */ { int *c; int ind; printf ( "\n" ); printf ( "subset_sum_find_test():\n" ); printf ( " subset_sum_find() seeks a subset of W that sums to T.\n" ); printf ( "\n" ); printf ( " Target value T = %d\n", t ); i4vec_print ( n, w, " Weight vector W:" ); c = subset_sum_find ( n, w, t, ind_min, ind_max, &ind ); if ( ind == -1 ) { printf ( "\n" ); printf ( " No solution was found.\n" ); } else { printf ( "\n" ); printf ( " Solution index = %d\n", ind ); i4vec_print ( n, c, " Solution:" ); } free ( c ); return ind; } /******************************************************************************/ void subset_sum_find_tests ( ) /******************************************************************************/ /* Purpose: subset_sum_find_tests() tests subset_sum_find_test(). Licensing: This code is distributed under the MIT license. Modified: 10 November 2015 Author: John Burkardt */ { int ind; int ind_max; int ind_min; int n; int t; int test; int test_num = 9; int *w; static int w01[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w02[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w03[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w04[10] = { 267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922 }; static int w05[21] = {518533, 1037066, 2074132, 1648264, 796528, 1593056, 686112, 1372224, 244448, 488896, 977792, 1955584, 1411168, 322336, 644672, 1289344, 78688, 157376, 314752, 629504, 1259008}; static int w06[10] = { 41, 34, 21, 20, 8, 7, 7, 4, 3, 3 }; static int w07[9] = { 81, 80, 43, 40, 30, 26, 12, 11, 9 }; static int w08[6] = { 1, 2, 4, 8, 16, 32 }; static int w09[10] = { 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 }; printf ( "\n" ); printf ( "subset_sum_find_tests():\n" ); printf ( " subset_sum_find_test() calls SUBSET_SUM_FIND\n" ); printf ( " with a particular set of problem data.\n" ); for ( test = 1; test <= test_num; test++ ) { if ( test == 1 ) { n = 8; w = i4vec_copy_new ( n, w01 ); t = 53; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 2 ) { n = 8; w = i4vec_copy_new ( n, w02 ); t = 53; ind_min = ind + 1; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 3 ) { n = 8; w = i4vec_copy_new ( n, w03 ); t = 53; ind_min = ind + 1; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 4 ) { n = 10; w = i4vec_copy_new ( n, w04 ); t = 5842; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 5 ) { n = 21; w = i4vec_copy_new ( n, w05 ); t = 2463098; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 6 ) { n = 10; w = i4vec_copy_new ( n, w06 ); t = 50; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 7 ) { n = 9; w = i4vec_copy_new ( n, w07 ); t = 100; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 8 ) { n = 6; w = i4vec_copy_new ( n, w08 ); t = 22; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } else if ( test == 9 ) { n = 10; w = i4vec_copy_new ( n, w09 ); t = 50; ind_min = 0; ind_max = i4_power ( 2, n ) - 1; } ind = subset_sum_find_test ( n, w, t, ind_min, ind_max ); free ( w ); } return; } /******************************************************************************/ int *subset_sum_table ( int t, int n, int w[] ) /******************************************************************************/ /* Purpose: subset_sum_table() sets a subset sum table. Discussion: The subset sum problem seeks to construct the value T by summing a subset of the values W. This function seeks a solution by constructing a table TABLE of length T, so that TABLE(I) = J means that the sum I can be constructed, and that the last member of the sum is an entry of W equal to J. Example: w = [ 1, 2, 4, 8, 16, 32 ]; t = 22; table = subset_sum ( w, t, r ) table = [ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16 ] Licensing: This code is distributed under the MIT license. Modified: 11 November 2015 Author: John Burkardt Input: int T, the target value. int N, the number of weights. int W[N], the weights. Output: int SUBSET_SUM_TABLE[T], the subset sum table. TABLE(I) is 0 if the target value I cannot be formed. It is J if the value I can be formed, with the last term in the sum being the value J. */ { int i; int j; int *table; table = ( int * ) malloc ( ( t + 1 ) * sizeof ( int ) ); for ( i = 0; i <= t; i++ ) { table[i] = 0; } for ( i = 0; i < n; i++ ) { for ( j = t - w[i]; 0 <= j; j-- ) { if ( j == 0 ) { if ( table[w[i]] == 0 ) { table[w[i]] = w[i]; } } else if ( table[j] != 0 && table[j+w[i]] == 0 ) { table[j+w[i]] = w[i]; } } } return table; } /******************************************************************************/ void subset_sum_table_test ( int t, int n, int w[] ) /******************************************************************************/ /* Purpose: subset_sum_table_test() tests subset_sum_table(). Licensing: This code is distributed under the MIT license. Modified: 11 November 2015 Author: John Burkardt Input: int T, the target value. int N, the number of weights. int W[N], a set of weights. The length of this array must be no more than 31. */ { int i; int *list; int m; int *table; printf ( "\n" ); printf ( "subset_sum_table_test():\n" ); printf ( " subset_sum_table() seeks a subset of W that sums to T.\n" ); printf ( "\n" ); printf ( " Target value T = %d\n", t ); i4vec_print ( n, w, " Weight vector W:" ); table = subset_sum_table ( t, n, w ); m = subset_sum_table_to_list_length ( t, table ); printf ( "\n" ); if ( m == 0 ) { printf ( " No solution was found.\n" ); } else { list = subset_sum_table_to_list ( t, table, m ); printf ( " %d = ", t ); for ( i = 0; i < m; i++ ) { if ( 0 < i ) { printf ( " + " ); } printf ( "%d", list[i] ); } printf ( "\n" ); free ( list ); } free ( table ); return; } /******************************************************************************/ void subset_sum_table_tests ( ) /******************************************************************************/ /* Purpose: subset_sum_table_tests() tests subset_sum_table_test(). Licensing: This code is distributed under the MIT license. Modified: 11 November 2015 Author: John Burkardt */ { int n; int t; int test; int test_num = 7; int *w; static int w01[8] = { 15, 22, 14, 26, 32, 9, 16, 8 }; static int w02[10] = { 267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922 }; static int w03[21] = { 518533, 1037066, 2074132, 1648264, 796528, 1593056, 686112, 1372224, 244448, 488896, 977792, 1955584, 1411168, 322336, 644672, 1289344, 78688, 157376, 314752, 629504, 1259008}; static int w04[10] = { 41, 34, 21, 20, 8, 7, 7, 4, 3, 3 }; static int w05[9] = { 81, 80, 43, 40, 30, 26, 12, 11, 9 }; static int w06[6] = { 1, 2, 4, 8, 16, 32 }; static int w07[10] = { 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 }; printf ( "\n" ); printf ( "subset_sum_count_tests():\n" ); printf ( " subset_sum_count_test() calls SUBSET_SUM_COUNT with\n" ); printf ( " a particular set of problem data.\n" ); for ( test = 1; test <= test_num; test++ ) { if ( test == 1 ) { t = 53; n = 8; w = i4vec_copy_new ( n, w01 ); } else if ( test == 2 ) { t = 5842; n = 10; w = i4vec_copy_new ( n, w02 ); } else if ( test == 3 ) { t = 2463098; n = 21; w = i4vec_copy_new ( n, w03 ); } else if ( test == 4 ) { t = 50; n = 10; w = i4vec_copy_new ( n, w04 ); } else if ( test == 5 ) { t = 100; n = 9; w = i4vec_copy_new ( n, w05 ); } else if ( test == 6 ) { t = 22; n = 6; w = i4vec_copy_new ( n, w06 ); } else if ( test == 7 ) { t = 50; n = 10; w = i4vec_copy_new ( n, w07 ); } subset_sum_table_test ( t, n, w ); free ( w ); } return; } /******************************************************************************/ int *subset_sum_table_to_list ( int t, int table[], int m ) /******************************************************************************/ /* Purpose: subset_sum_table_to_list() converts a subset sum table to a list. Discussion: The subset sum problem seeks to construct the value T by summing a subset of the values W. This function takes a table computed by subset_sum_table() and converts it to the corresponding list of values that form the sum. Example: t = 22 n = 6 w = [ 1, 2, 4, 8, 16, 32 ] call subset_sum ( t, n, w, table ) table = [ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16 ] call subset_sum_table_to_list ( t, table, m, list ) m = 3 list = [ 2, 4, 16 ] Licensing: This code is distributed under the MIT license. Modified: 11 November 2015 Author: John Burkardt Input: int T, the target value. int TABLE(T), the subset sum table. int M, the number of items in the list. Output: int LIST[M], the weights that sum to T. */ { int i; int *list; /* Create list. */ list = ( int * ) malloc ( m * sizeof ( int ) ); /* Populate list. */ i = t; m = 0; while ( 0 < i ) { list[m] = table[i]; m = m + 1; i = i - table[i]; } return list; } /******************************************************************************/ int subset_sum_table_to_list_length ( int t, int table[] ) /******************************************************************************/ /* Purpose: subset_sum_table_to_list_length() returns the length of a list. Discussion: The subset sum problem seeks to construct the value T by summing a subset of the values W. This function takes a table computed by subset_sum_table() and converts it to the corresponding list of values that form the sum. Example: t = 22 n = 6 w = [ 1, 2, 4, 8, 16, 32 ] call subset_sum ( t, n, w, table ) table = [ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16 ] call subset_sum_table_to_list ( t, table, m, list ) m = 3 list = [ 2, 4, 16 ] Licensing: This code is distributed under the MIT license. Modified: 11 November 2015 Author: John Burkardt Input: integer T, the target value. integer TABLE[T], the subset sum table. Output: int SUBSET_SUM_TABLE_TO_LIST_LENGTH, the number of items in the list. If M == 0, then no solution was found and the list is empty. */ { int i; int m; /* Determine length of list. */ i = t; m = 0; while ( 0 < i ) { m = m + 1; i = i - table[i]; } return m; }