” 写作CS 325编程语言、 辅导PythonHomework 3Problem 1 (3 points)Rod Cutting: Show, by means of a counterexample, that the following greedy strategy does notalways 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 lengthi, where 1 i n, having maximum density. It then continues by applying the greedy strategy tothe remaining piece of length n i.Problem 2 (3 points)Modified Rod Cutting: Consider a modification of the rod-cutting problem in which, in additionto a price pi for each rod, each cut incurs a Fixed cost of c. The revenue associated with a solutionis now the sum of the Prices of the pieces minus the costs of making the cuts. Give a dynamicprogrammingalgorithm (pseudocode) to solve this modified problem.Problem 3 (6 points)Making Change: Given coins of denominations (value) 1 = v1 v2 vn, we wish to makechange for an amount A using as few coins as possible. Assume that vis and A are integers.Since v1= 1 there will always be a solution. Formally, an algorithm for this problem should takeas input an array V where V[i] is the value of the coin of the ith denomination and a value Awhich is the amount of change we are asked to make. The algorithm should return an array Cwhere C[i] is the number of coins of value V[i] to return as change and m the minimum numberof coins it took. You must Return exact change so V[i] C[i] = A=1The 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 minimumnumber 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 familywins a shopping spree each person in the family can take any items in the store that he or she cancarry out, however each person can only take one of each type of item. For example, one familymember can take one television, one watch and one toaster, while another family member cantake one television, One camera and one pair of shoes. Each item has a price (in dollars) and aweight (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 itemsfor 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 maximumtotal 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, afamily 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 shouldsatisfy 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 thenumber 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) correspondsto the weight of object. The next line contains one integer (1 F 30) which is the number of people in thatfamily. The next F lines contains The maximum weight (1 M 200) that can be carried by the ithperson in the family (1 i F).Output: Written to a file named results.txt. For each test case your program should output themaximum total price of all goods that the family can carry out during their shopping spree andfor each the family Member, numbered 1 i F, list the item numbers 1 N 100 that theyshould 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 cases3 // 3 items for test case 172 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 264 26 // P and W of item 1 (case 2)Sample Output (in some cases, there are multiple solutions, providing only one of thesesolutions is enough)如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
