Description

Introduction
In this programming assignment, you will continue practicing implementing dynamic programming solutions.
Passing Criteria: 2 out of 3
Passing this programming assignment requires passing at least 2 out of 3 programming challenges from this assignment. In turn, passing a programming challenge requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
Contents
1 Maximum Amount of Gold 2
2 Partitioning Souvenirs 3
3 Maximum Value of an Arithmetic Expression 4

1 Maximum Amount of Gold
Problem Introduction
You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).
Problem Description
Task. Given n gold bars, find the maximum weight of gold that fits into a bag of capacity W.
Input Format. The first line of the input contains the capacity W of a knapsack and the number n of bars of gold. The next line contains n integers w0,w1,…,wn−1 defining the weights of the bars of gold.
Constraints. 1 ≤ W ≤ 104; 1 ≤ n ≤ 300; 0 ≤ w0,…,wn−1 ≤ 105.
Output Format. Output the maximum weight of gold that fits into a knapsack of capacity W.
Sample 1.
Input:
103
148
Output:
9
Here, the sum of the weights of the first and the last bar is equal to 9.
Starter Files
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
2 Partitioning Souvenirs
You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.
Problem Description
Input Format. The first line contains an integer n. The second line contains integers v1,v2,…,vn separated by spaces.
Constraints. 1 ≤ n ≤ 20, 1 ≤ vi ≤ 30 for all i.
Output Format. Output 1, if it possible to partition v1,v2,…,vn into three subsets with equal sums, and 0 otherwise.
Sample 1.
Input:
4
3333
Output:
0
Sample 2.
Input:
1
40
Output:
0
Sample 3.
Input:
11
17593457172367118259
Output:
1
34+67+17 = 23+59+1+17+18 = 59+2+57.
Sample 4.
Input:
13
12345577810121925
Output:
1
1+3+7+25 = 2+4+5+7+8+10 = 5+12+19.
3 Maximum Value of an Arithmetic Expression
Problem Introduction
In this problem, your goal is to add parentheses to a given arithmetic
expression to maximize its value. max(5−8+7×4−8+9) =?
Problem Description
Task. Find the maximum value of an arithmetic expression by specifying the order of applying its arithmetic operations using additional parentheses.
Input Format. The only line of the input contains a string s of length 2n +1 for some n, with symbols s0,s1,…,s2n. Each symbol at an even position of s is a digit (that is, an integer from 0 to 9) while each symbol at an odd position is one of three operations from {+,-,*}.
Constraints. 1 ≤ n ≤ 14 (hence the string contains at most 29 symbols).
Output Format. Output the maximum possible value of the given arithmetic expression among different orders of applying arithmetic operations.
Sample 1.
Input:
1+5
Output:
6
Sample 2.
Input:
5-8+7*4-8+9
Output:
200
200 = (5−((8+7)×(4−(8+9))))
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.