Programming Assignment 6:Dynamic Programming 2 Solution

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    gold bars, find the maximum weight of gold that fits into a bag of capacity    .

Input Format. The first line of the input contains the capacity of a knapsack and the number of bars of gold. The next line contains integers 0, 1, . . . , −1 defining the weights of the bars of gold.

Constraints. 1 ≤    ≤ 104; 1 ≤    ≤ 300; 0 ≤  0, . . . ,    −1 ≤ 105.

Output Format. Output the maximum weight of gold that fits into a knapsack of capacity    .

Sample 1.

Input:

    10 3

1 4 8

Output:


9

Here, the sum of the weights of the first and the last bar is equal to 9.

Starter Files

Starter files contain an implementation of the following greedy strategy: scan the list of given bars of gold and add the current bar if it fits into the current capacity (note that, in this problem, all the items have the same value per unit of weight, for a simple reasons: they are all made of gold). As you already know from the lectures, such a greedy move is not safe. You may want to additionally submit a starter file as a solution to the grading system to ensure that this greedy algorithm indeed might produce a non-optimal result.

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 . The second line contains integers 1, 2, . . . , separated by spaces.

Constraints. 1 ≤    ≤ 20, 1 ≤    ≤ 30 for all .

Output Format. Output 1, if it possible to partition 1, 2, . . . , 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 of length 2 + 1 for some , with symbols 0, 1, . . . , 2 . Each symbol at an even position of 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 ≤    ≤ 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.



















4