Question

Pinky and The Brain are great friends. They like to play games with numbers. This time, Pinky has given The Brain a list of numbers and given him the task of determining if it is possible to choose a subset of them such that they sum is equal to another given number.

Build an algorithm using dynamic programming to help The Brain with his problem.

INPUT

- The first line corresponds to N, the amount of numbers given by Pinky
- The next N lines contain each of the numbers
- The last line contains the desired sum

OUTPUT

- True or False (Whether is possible to obtain the desired sum or not)

**Sample Input 1:**

39

15

88

3

43

40

100

45

34

89

10

17

70

14

63

92

24

64

6

42

12

81

34

38

63

35

77

67

80

5

58

46

17

67

21

73

10

49

21

54

128

**Sample Output 1:**

True

**Sample Input 2:**

30

72

21

33

6

72

53

71

28

66

92

90

73

33

10

70

25

96

82

85

53

58

61

76

20

85

4

1

7

34

76

670

**Sample Output 2:**

True

**Sample Input 3:**

35

8

63

89

6

83

78

31

5

46

95

59

73

98

47

43

16

44

50

32

5

77

23

30

44

69

94

24

14

50

99

82

90

1

21

25

557

**Sample Output 3:**

True

**Sample Input 4:**

38

2

24

70

51

24

51

98

9

81

55

11

50

94

42

91

94

8

64

86

20

25

34

100

65

30

49

99

47

63

20

3

61

5

100

86

22

94

60

1766

**Sample Output 4:**

True

**Sample Input 5:**

21

29

53

31

74

21

57

35

67

10

86

60

46

17

52

38

21

14

51

26

12

86

647

**Sample Output 5:**

True

Write a program, test using stdin → stdout

Answer #1

import java.util.*;

public class Solution {

static boolean checkSubset(int[] arr, int n, int sum)

{

boolean mat[][] = new boolean[sum + 1][n + 1];

for (int i = 0; i <= n; i++)

mat[0][i] = true;

for (int i = 1; i <= sum; i++)

mat[i][0] = false;

for (int i = 1; i <= sum; i++) {

for (int j = 1; j <= n; j++) {

mat[i][j] = mat[i][j - 1];

if (i >= arr[j - 1])

mat[i][j] = mat[i][j] || mat[i - arr[j - 1]][j - 1];

}

}

return mat[sum][n]; }

public static void main(String[] args) {

int n;

int[] arr;

int sum;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

arr = new int[n];

for (int i = 0; i < n; i++) {

arr[i] = scanner.nextInt();

}

sum = scanner.nextInt();

System.out.print(checkSubset(arr, n, sum));

scanner.close();

}

}

Hi,If you like the solution please press the thumb up button.

70, 35, 86, 81, 63, 71, 58, 53, 99, 85, 64, 56, 17, 38, 94, 78,
101, 71, 63, 65, 58, 49, 88, 70, 51, 61, 80, 67, 53, 74, 73, 29,
64, 48, 98, 78, 67, 65, 76, 59, 50, 65, 98, 91, 66, 64, 69, 86, 63,
74. Construct an ungrouped frequency distribution from these data.
Start with the highest score ( X) and proceed down to the lowest
score. the f column will indicate the frequency or...

A court administrator wants to examine burglary case disposition
times in his city. A random sample of 50 burglary cases disposed of
during the previous year is drawn. The numbers that follow
represent the number of days needed for each case:
70, 35, 86, 81, 63, 71, 58, 53, 99, 85, 64, 56, 17, 38, 94, 78,
101, 71, 63, 65, 58, 49, 88, 70, 51, 61, 80, 67, 53, 74, 73, 29,
64, 48, 98, 78, 67, 65, 76,...

Using the accompanying Student Grades data, construct a scatter
chart for midterm versus final exam grades and add a linear
trendline. What is the model? If a student scores 7878 on the
midterm, what would you predict her grade on the final exam to
be?
Student
Midterm
Final Exam
1
75
64
2
85
91
3
80
68
4
88
83
5
76
60
6
67
80
7
78
74
8
95
94
9
67
61
10
93
87
11...

Student Grades
Student
Test
Grade
1
76
62
2
84
90
3
79
68
4
88
84
5
76
58
6
66
79
7
75
73
8
94
93
9
66
65
10
92
86
11
80
53
12
87
83
13
86
49
14
63
72
15
92
87
16
75
89
17
69
81
18
92
94
19
79
78
20
60
71
21
68
84
22
71
74
23
61
74
24
68
54
25
76
97...

This dataset contains consumer responses indicating the number
of times they had to send their product for repair and their
satisfaction with the repair process. Create a graph which can be
used to visually demonstrate the relationship between the two
columns of data. Ensure that the chart is professional with
appropriate titles, axis labels, etc. Note any observations you see
in your visualization (type these as sentences directly into an
Excel cell(s)).
Sample
Satisfaction Rating
Repair Requests
1
63%
13...

Dataset:
Husband Wife
53 50
38 34
46 44
30 36
31 23
26 31
29 25
48 51
65 46
29 26
28 23
29 32
25 22
22 21
21 24
43 50
24 27
38 33
33 26
35 29
40 29
27 25
27 24
49 38
48 39
27 27
26 24
40 34
35 37
21 26
32 39
30 28
60 52
36 40
25 23
66 55
52 34
41 40
43 ...

Question 2:
Write a C program that read 100 integers from the attached file
(integers.txt) into an array and copy the integers from the array
into a Binary Search Tree (BST). The program prints out the
following:
The number of comparisons made to search for a given integer in the
BST
And
The number of comparisons made to search for the same integer in
the array
Question 3
Run the program developed in Question 2 ten times. The given values...

Below are 36 sorted ages of an acting award winner. Find
P90
using the method presented in the textbook.
19
21
21
22
24
25
26
28
34
37
37
40
40
41
41
42
43
45
46
49
51
53
55
62
63
67
68
69
69
73
74
74
75
76
76
78

Below represent scores on an exam, each entry one score for one
student
40
99
59
98
63
63
64
65
67
35
67
67
68
70
71
71
71
46
72
72
60
73
74
74
74
75
97
75
62
76
76
76
76
76
77
57
77
98
77
63
78
78
78
79
79
80
80
80
80
80
81
81
92
81
93
82
82
83
83
83
83
83
83
83
84
84
84...

1) Given the data set below
25 52 67 23 78 89 57 90 32 77
45 48 62 54 94 69 46 79 40 33
21 57 84 54 23 34 68 63 61 76
87 78 39 50 70 60 32 65 73 45
28 82 66 79 71 80 46 66 24 90
a) Construct a Frequency Distribution with 8 classes and a class
width of 10
b) Construct a Relative Frequency distribution from the frequency
distribution...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 12 minutes ago

asked 16 minutes ago

asked 18 minutes ago

asked 25 minutes ago

asked 26 minutes ago

asked 37 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago