Reference no: EM132226959
You can write your programs using any programming language you prefer. Upload your programs (source code) and screen dumps that show your program execution
Question 1. Given a string of characters, count the number of substrings that start with an A and end with a B. For example, there are four such substrings in CABAAXBYA, i.e. AB, ABAAXB, AAXB, AXB. Write a program that uses the brute-force approach to count the number of such substrings in a given string.
A sample dialogue might look like as follows:
Please enter a string: ADABCBA
The number of substrings that start with an A and end with a B is 4
Question 2. Write a program that uses the brute-force approach to solve the 0/1 knapsack problem. Suppose there are n items with weights w1, w2, ..., wn and values v1, v2, ..., vn and a knapsack of capacity W. Use the decrease-by-one technique to generate the power set and calculate the total weights and values of each subset, then find the largest value that fits into the knapsack and output that value.
For example: If there are 3 items with the following weights and values:
weight: 8 4 5
value: 20 10 11
and the capacity of the knapsack is 9, your program should then calculate the total weight and the total value of each subset in the power set:
total weight of subset: 0, 8, 4, 12, 5, 13, 9, 17
total value of subset: 0, 20, 10, 30, 11, 31, 21, 41
The largest value that fits into the knapsack: 21.