MTH4300 Home

Recursion improvements with maps

Problem 1. The user input consists of two positive integers \(n\) and \(M\) and two sequences \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\) and \(w[0]\), \(w[1]\), \(\dots\), \(w[n-1]\) of positive integers. The numbers \(w[0]\), \(w[1]\), \(\dots\), \(w[n-1]\) are the weights of the items \(0\), \(1\), \(\dots\), \(n-1\). The numbers \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\) are the values of the items. The number \(M\) is the maximal weight that can fit in a backpack. Create the program that calculates the largest value that can fit in the backpack and prints the items that need to be selected to achieve this largest value.

Problem 2. The user input consists of positive integers \(M\) and \(n\), and a sequence \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\) of positive integers. The person with \(M\) dollars decided to go to store and to spend all of the money. The person has a shopping list of items whose prices are \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\). Create the program that determines whether the person can choose a subset of items from the list whose total price is exactly equal to \(M\). If it is possible to spend all the money, then the program should also print the list of the items that need to be bought in order to spend the money.