首页 >
> 详细

Homework 3

Problem 1 (3 points)

Rod Cutting: Show, by means of a counterexample, that the following “greedy” strategy does not

always determine an optimal way to cut rods. Define the density of a rod of length i to be pi / i,

that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length

i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to

the remaining piece of length n – i.

Problem 2 (3 points)

Modified Rod Cutting: Consider a modification of the rod-cutting problem in which, in addition

to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution

is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamicprogramming

algorithm (pseudocode) to solve this modified problem.

Problem 3 (6 points)

Making Change: Given coins of denominations (value) 1 = v1 < v2 < … < vn, we wish to make

change for an amount A using as few coins as possible. Assume that vi’s and A are integers.

Since v1= 1 there will always be a solution. Formally, an algorithm for this problem should take

as input an array V where V[i] is the value of the coin of the ith denomination and a value A

which is the amount of change we are asked to make. The algorithm should return an array C

where C[i] is the number of coins of value V[i] to return as change and m the minimum number

of coins it took. You must return exact change so ∑ V[i] ∙ C[i] = A

𝑛

𝑖=1

The objective is to minimize the number of coins returned or: 𝑚 = 𝑚𝑖𝑛 ∑ C[i]

𝑛

𝑖=1

(a) Describe and give pseudocode for a dynamic programming algorithm to find the minimum

number of coins needed to make change for A.

(b) What is the theoretical running time of your algorithm?

Problem 4 (18 points)

Acme Super Store is having a contest to give away shopping sprees to lucky families. If a family

wins a shopping spree each person in the family can take any items in the store that he or she can

carry out, however each person can only take one of each type of item. For example, one family

member can take one television, one watch and one toaster, while another family member can

take one television, one camera and one pair of shoes. Each item has a price (in dollars) and a

weight (in pounds) and each person in the family has a limit in the total weight they can carry.

Two people cannot work together to carry an item. Your job is to help the families select items

for each person to carry to maximize the total price of all items the family takes.

(a) Write an efficient algorithm (verbal description and pseudo-code) to determine the maximum

total price of items for each family and the items that each family member should select.

(b) What is the theoretical running time of your algorithm for one test case given N items, a

family of size F, and family members who can carry at most Mi pounds for 1 ≤ i ≤ F.

(c) Implement your algorithm by writing a program named “shopping”. The program should

satisfy the specifications below.

Input: The input file named “shopping.txt” consists of T test cases

T (1 ≤ T ≤ 100) is given on the first line of the input file.

Each test case begins with a line containing a single integer number N that indicates the

number of items (1 ≤ N ≤ 100) in that test case

Followed by N lines, each containing two integers: P and W. The first integer (1 ≤ P ≤

5000) corresponds to the price of object and the second integer (1 ≤ W ≤ 100) corresponds

to the weight of object.

The next line contains one integer (1 ≤ F ≤ 30) which is the number of people in that

family.

The next F lines contains the maximum weight (1 ≤ M ≤ 200) that can be carried by the ith

person in the family (1 ≤ i ≤ F).

Output: Written to a file named “results.txt”. For each test case your program should output the

maximum total price of all goods that the family can carry out during their shopping spree and

for each the family member, numbered 1 ≤ i ≤ F, list the item numbers 1 ≤ N ≤ 100 that they

should select. List both family members and the corresponding items in order.

Sample Input (comments are not part of the file, they are added for clarification)

2 // 2 test cases

3 // 3 items for test case 1

72 17 // P and W of item 1 (case 1)

44 23 // P and W of item 2 (case 1)

31 24 // P and W of item 3 (case 1)

1 // 1 family member (case 1)

26 // max weight for family member 1 (case 1)

6 // 6 items for test case 2

64 26 // P and W of item 1 (case 2)

Sample Output (in some cases, there are multiple solutions, providing only one of these

solutions is enough)

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28