Problem $3(280$ pts$).$

Note: You may use Java or Python. However, you must use only standard libraries. This means only what is implicitly loaded by default for your choice of language. In general, it is expected that you can perform all necessary tasks using only standard IO functionality, basic data types, etc. In particular, it is disallowed to use scientific computing libraries, or any libraries having functionalities designed to solve the problem you are given. If feel you need a library to utilize a fundamental data type or structure, or when in any doubt, ask the instructor for permission first. Otherwise, stiff penalties can be expected.

The Problem: You work for an up and coming web hosting company, Host$-$R$-$Us$.$ Your business model centers around placing advertising on a certain number of each of your clients' served pages. You have a list of potential clients, and for each you have an expected amount of advertising revenue per month, as well as an expected amount of bandwidth consumption. You have a fixed amount of bandwidth available to lease, and it is your goal to maximize profit at the end of the month. You cannot host all clients, so you will be forced to choose who to host, and as a result will be forced to not host some potential clients.

At the same time, you also have an agreement with another web hosting company, Host$-$A$-$Rama, to assume the balance of a single lease you cannot meet, for a $50$ percent surcharge. Put another way, you can take on one client knowing that you have exceeded your bandwidth cap in doing so$,$ and then pass what portion you can't handle to Host$-$A$-$Rama, paying them $\backslash (150\backslash \%\backslash )$ of what you charge that client for the portion you cannot host.

The Input Format: Your program will be expected to read input from a text file, the name of which should be passed as the first parameter to your program on command line invocation. This file will contain string representations of positive integers $($note that the grader is written in Python encoding, whose default encoding is UTF$-8).$ The output will need to be written in the same format.

The first line of the file will be a $($string$)$ integer indicating your companies' total available bandwidth for lease. The second line of the file will be an integer indicating how many lines of input will follow. The third, and all subsequent lines, will each represent a potential client, and will consist of two $($string$)$ numbers separated by a comma, with no whitespace. The first of these numbers will indicate the expected monthly advertising revenue for this client, and the second will represent the expected monthly bandwidth demand by this client. The third line will be considered to represent client $0,$ and the client IDs will increment with each line $($e$.$g$.$ client $74\text{'}$s data will appear on line $77$ of the file$).$

You can expect your program to be tested on randomized input on the order of $\backslash (2^\{15\}\backslash )$ clients, and $\backslash (2^\{12\}\backslash )$ dollars revenue, and $\backslash (2^\{12\}\backslash )$ units of bandwidth.

Your Program's Output: Your program will be expected to output a text file named output.txt$,$ in the string format described above. The first line of output will be either $0$ or $1$: $0$ if you did not sublease a client to Host$-$A$-$Rama, and $1$ if you did. If you did sublease, the next line will contain the subleased client's ID number, followed immediately by a comma, and then the amount of bandwidth you are subleasing to Host$-$A$-$Rama. The following line will be an integer representing the number of lines which follow $($the number of clients you will take on in full$).$ Each remaining line will contain exactly one client ID$,$ uniquely representing one of the clients whom you are taking on in full.

Note: Full credit will be awarded to an almost optimal solution, but up to $\backslash (20\backslash \%\backslash )$ bonus is available for exceeding this. Hint: you shouldn't really expect to lose too much money subleasing just a single client with so many choices.

Note : Also if I run the code with the given input the ouput doesn't match please explain that as well. Is there a possibility that there might be multiple possible outputs.

Problem $4(160$ pts$).$

Suppose you are still working for Host$-$R$-$Us$,$ but now Host$-$A$-$Rama has decided to terminate its agreement

with you to buy partial hosting contracts. This means that if$,$ at the end of the month, your roster of clients

leaves available bandwidth unused, then you simply lose the potential revenue. Design a dynamic programming

algorithm to maximize profit in this new scenario.