The following submission rules apply: · For those questions requiring programs,
ID: 3791780 • Letter: T
Question
The following submission rules apply:
· For those questions requiring programs, the solutions must be implemented using JavaScript or Java.
o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.
o Solutions must be provided in plain text so that formatting is not lost.
· All answers must be provided in this document.
· Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.
1 Give pseudocode for a non-recursive backtracking procedure for solving the sum of subsets problem, based on the state-space tree given in Figure 10.4.
PART ll: Major Design Strategies ono I 10 1 0 0 1 0 0 0 0 no 0 0 0 1 0 (1,0,0,1,0) (0,1,1,0,0) (1,1,0,1,1) FIGURE 10.4 Fixed-tuple T modeling the decision set D, given by Formula (10.1.2) for the sum of subsets problem with n 5. Edges ending at level k are labeled 1 or 0, depending on whether was chosen or not. of the path from the root to some sample leaf nodes shown. a single lifetime, even for relatively small input sizes. However, we can de termine that there is no goal node in often the tree. the subtree rooted at a given he state-space In this case, we say that node X p searching tree by eliminating the bounded, and we can Boolean state-space trees, we descendants of node X. Thus, such look for good bounding funcions Rounded is that if BoundaduExplanation / Answer
#include <stdio.h>
#include <stdlib.h>
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
static int total_nodes;
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}
printf(" ");
}
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;
if( target_sum == sum )
{
printSubset(t, t_size);
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
return;
}
else
{
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}
int main()
{
int weights[] = {10, 7, 5, 18, 12, 20, 15};
int size = ARRAYSIZE(weights);
generateSubsets(weights, size, 35);
printf("Nodes generated %d ", total_nodes);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.