Description
Problem Definition Your job is to write a program to help a thief choose which items to steal1 . The input is a set of items that the thief can steal. Each item has a weight and a value associated with it. Of course, the thief would like to steal items whose collective value is maximum, but since the thief has planned an arduous escape route, he can only carry a certain maximum weight. Thus our input includes a total weight that the thief can carry. Your program should output the items that he must steal such that 1. the total value is maximized, but 2. the total weight is not more than the weight that the thief can carry. Please follow the steps given below. 0.1 Command Line Arguments Your program should be written such that the name of the input file can be given as a command line argument. To set the command line argument from within Netbeans2 , go to Run → Set Project Configurations → Customize. Choose Run on the left panel. You will see a Run Command on the right panel and “${OUTPUT PATH}” against the Run Command. Modify it to 1This is just a programming exercise. Please do not attempt this in real life. If you do, ensure that the solution is absolutely correct — you don’t want an angry thief coming after you. 🙂 2 If you use something other than Netbeans, you can use the traditional command line interface. 1 “${OUTPUT_PATH}” CLG Where CLG is the command line argument. In our case, CLG must be the full path and name of the input file. One thing to note is that CLG must come outside the quotations. When no input file name is given, then the input must be read from the console. 0.2 The Input Format Regardless of whether your input is read from a file or from the console, it should have the following format. (Note that all numbers are integers.) . . . For example, 7 5 Gold 3 100 Silver 4 110 Bronze 7 50 Platinum 2 90 Plutonium 1 130 To store the items, create a struct as follows: typedef struct it { char name[MAX]; int weight; int value; } item; Then, you can read the items and store them in an array. Ensure that all your arrays can hold up to at least 50 elements. This includes char arrays that you will use for strings. 0.3 Recursive Enumeration of Subsets Write a recursive function to enumerate every subset of items. This is based on the idea of enumerating every bit string of n bits. 0.4 How much can the thief steal? Maintain a running maximum value max that can be stolen by the thief. Initialize max to 0. For each subset S of items, check if the total weight of items in S is below the capacity. If yes, compute the total value of items in S and it exceeds max, update max. (You are also required to adapt this solution to keep track of the actual subset of items that the thief must steal.) 2 0.5 Output Format Your final output must be printed on the screen all in one line . The format is as follows: The above example input should give you the following output. 330 Silver Platinum Plutonium Note that the order of the items is important — it should be in the same order in which the items were listed in the input. For example, the following will be considered wrong output. 330 Platinum Plutonium Silver Why are we picky about the formatting? We are going to automate the evaluation process. Your output will be checked with the standard “correct” output. If you format it incorrectly, then your output will not match the expected output and thus you will lose marks. Uploading into MOODLE Your code should be written as a single .c file. This file must be uploaded into moodle. A link has been set up for this purpose in moodle. Your TA for this lab CS08B031, CS10B052, CS11B001 — CS11B009 Tejas Kulkarni CS11B011 — CS11B021 Paresh Nakhe CS11B022 — CS11B032 Shrikant Polawar CS11B033 — CS11B042 Sai Sreennivas CS11B043 — CS11B053 Nishaanth CS11B054 — CS11B063 Saurav Kant Jha 3
