Java代写：COMPSCI320-Assignment4-DynamicProgramming

发表于 | 分类于
使用Java完成

Computer Science 732

Programming Assignment 4

Requirements

This programming assignment will test your ability to design a dynamic programming solution to a simple problem. It is worth 5% of your total course marks. Please try and test with your own generated input cases before submitting to the automated marker.

Problem: Split Necklace Jewels

We have a Queen with several Necklaces that she wants to split-up and divide the jewel stones to his two daughters as fairly as possible. Each jewel on an necklace has a fixed value and she has decided to let one daughter pick a subset of the jewels then the other daughter take the remaining. The “fairness idea’ that the Queen decides to use is to restrict the first daughter to pick only a subset of jewels
that are not adjacent to any others in that set. The jewels are in a circular pattern in index positions 0 , 1 , 2 ,… , n−1. Where if the first daughter selects jewel at positionithen she can not take jewel at
positioni−1 ori+ 1 (modulon). The maximum number of jewels per necklace is one million.

An input (taken from keyboard) for you to process is a sequence of necklaces, one per line. Each necklaces is a sequence of positive integers separated by white spaces denoting the values of each jewel.

The printed output of your program, one line per each scenario, is the maximum value daughter one can obtain and the remaining value the other daughter receives for each necklace.

1
Sample Input:
1
2
3
4
4 10 8
10 4 8 5
3 2 10 2 3 7
1 1 1 1 1
1
Sample Output
1
2
3
4
10 12
18 9
17 10
2 3

Submission

There will be three cases on the automarker of increasing difficulty. These will be worth 2, 2 and 1 marks, respectively. You need to submit your program as a group submission for up to 10 submission tries.