I need help with this c++ problem. I dont really understand it. Thank you in adv

Question

I need help with this c++ problem. I dont really understand it.  Thank you in advance.

Part I: Create and print out the two arrays: (Be sure to do this first)

Anne           30

         Bob             150

         Ralph          305

         Tim             225

         Barbara       135

         Jane            160

         Steve          80

         Tom            200

         Mike            165

         Shirley                  90

         Pam            100

         Frank          120

Part II:  The elevators in our building have an 1100 lb. load limit.  Determine which people in the list above get on the elevator. Print their names, weights, total weight, and how many got on.  

         

Part III:  Rearrange these people in ascending sequence by weight and print the two arrays.  Determine again how many may ride the elevator, printing out their names, weights, total weight and the number of how many people got on.

Part IV:  Rearrange these people in ascending sequence by name (USE A DIFFERENT SORT ALGORITHM THAN THE ONE YOU USED IN PART II) and print the two arrays.  Determine again how many may ride the elevator, printing out their names, weights, total weight and the number of how many people got on.

Part V:  Have the program determine which method allowed the most people to get on the elevator. The program should compare the three different counts of how many people got on the elevator.

This program should include 2 sort methods, a method to determine how many people get on the elevator (will be called 3 times), and a print method which prints both arrays (include a size parameter and it can be called 6 times).

Turn in an algorithm for main, source code, and output.

NOTE: You may hard code the data into the arrays and print the answers on the screen.

EXTRA CREDIT: Read the data from a file and put the results on an output file.  Print the output file using Notepad or some other editor.

Explanation / Answer

//I have written the program in java..

a knapsack has a capacity (your elevator can lift 1100lbs), a person takes up capacity (their weight) and have a value (all equal for each person). How to fill up the knapsack given the capacity constraint so that the sum of the values is maximized (read: as many peoply can be stuffed in that elevator).

A person is either stuffed in that elevator or not. When s/he is, the problem is reduced to a lesser capacity and a set of persons minus this current person. When a person doesn't fit in the elevator obviously we don't even try to stuff him in. That's how my program works. It reads the following data file:

Java Code: 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 The first line contains the capacity of the elevator and the number of persons. The following lines are the values of the persons and their weight. I saved this file in c:/tmp/data.txt

Here is the class:

Java Code: import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class Knapsack {
private Item[] items; private int nofItems, capacity;
private void initialize() throws FileNotFoundException {
Scanner input= new Scanner(new File("c:/tmp/data.txt"));
capacity= input.nextInt(); nofItems= input.nextInt(); items= new Item[nofItems]; for (int i= 0; i < nofItems; i++) items[i]= new Item(input.nextInt(), input.nextInt());
total= 0L; cut= 0L; }
private Solution solve(int allowed, int cap) {
Solution take, dontTake;
if (allowed < 0) return new Solution(nofItems);
total++;
dontTake= solve(allowed-1, cap);
if (items[allowed].weight > cap) { cut++; return dontTake; }
take= solve(allowed-1, cap-items[allowed].weight).take(items, allowed);
return (take.value > dontTake.value)?take:dontTake; }
private long total; private long cut;
public static void main(String[] args) throws FileNotFoundException {
Knapsack k= new Knapsack(); k.initialize();
Solution b = k.solve(k.nofItems-1, k.capacity);
System.out.println("Total Value: " + b.value); System.out.println("Total Steps: " + k.total); System.out.println("Total Cuts : " + k.cut); int w= 0; for (int i= 0; i < k.nofItems; i++) { if (b.taken[i]) { System.out.println(i + ": " + k.items[i]); w+= k.items[i].weight; } } System.out.println("Total weight: "+w); } }
class Solution {
boolean[] taken; int value;
Solution(int nofItems) { this.taken= new boolean[nofItems]; }
Solution take(Item[] items, int rank) {
this.value+= items[rank].value; this.taken[rank]= true; return this; } }
class Item {
int value, weight;
public Item(int value, int weight) { this.value= value; this.weight= weight; }
public String toString() { return value + " " + weight; } }
OUTPUT:
Total Value: 9 Total Steps: 3526 Total Cuts : 342 0: 1 30 1: 1 150 3: 1 225 4: 1 135 5: 1 160 6: 1 80 9: 1 90 10: 1 100 11: 1 120 Total weight: 1090
//I have written the program in java..

a knapsack has a capacity (your elevator can lift 1100lbs), a person takes up capacity (their weight) and have a value (all equal for each person). How to fill up the knapsack given the capacity constraint so that the sum of the values is maximized (read: as many peoply can be stuffed in that elevator).

A person is either stuffed in that elevator or not. When s/he is, the problem is reduced to a lesser capacity and a set of persons minus this current person. When a person doesn't fit in the elevator obviously we don't even try to stuff him in. That's how my program works. It reads the following data file:

Java Code: 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 The first line contains the capacity of the elevator and the number of persons. The following lines are the values of the persons and their weight. I saved this file in c:/tmp/data.txt

Here is the class:

Java Code: import java.io.File; Java Code: 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 Java Code: 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120 Java Code: import java.io.FileNotFoundException; import java.util.Scanner;
public class Knapsack {
private Item[] items; private int nofItems, capacity;
private void initialize() throws FileNotFoundException {
Scanner input= new Scanner(new File("c:/tmp/data.txt"));
capacity= input.nextInt(); nofItems= input.nextInt(); items= new Item[nofItems]; for (int i= 0; i < nofItems; i++) items[i]= new Item(input.nextInt(), input.nextInt());
total= 0L; cut= 0L; }
private Solution solve(int allowed, int cap) {
Solution take, dontTake;
if (allowed < 0) return new Solution(nofItems);
total++;
dontTake= solve(allowed-1, cap);
if (items[allowed].weight > cap) { cut++; return dontTake; }
take= solve(allowed-1, cap-items[allowed].weight).take(items, allowed);
return (take.value > dontTake.value)?take:dontTake; }
private long total; private long cut;
public static void main(String[] args) throws FileNotFoundException {
Knapsack k= new Knapsack(); k.initialize();
Solution b = k.solve(k.nofItems-1, k.capacity);
System.out.println("Total Value: " + b.value); System.out.println("Total Steps: " + k.total); System.out.println("Total Cuts : " + k.cut); int w= 0; for (int i= 0; i < k.nofItems; i++) { if (b.taken[i]) { System.out.println(i + ": " + k.items[i]); w+= k.items[i].weight; } } System.out.println("Total weight: "+w); } }
class Solution {
boolean[] taken; int value;
Solution(int nofItems) { this.taken= new boolean[nofItems]; }
Solution take(Item[] items, int rank) {
this.value+= items[rank].value; this.taken[rank]= true; return this; } }
class Item {
int value, weight;
public Item(int value, int weight) { this.value= value; this.weight= weight; }
public String toString() { return value + " " + weight; } }
OUTPUT:
Total Value: 9 Total Steps: 3526 Total Cuts : 342 0: 1 30 1: 1 150 3: 1 225 4: 1 135 5: 1 160 6: 1 80 9: 1 90 10: 1 100 11: 1 120 Total weight: 1090
Total Value: 9 Total Steps: 3526 Total Cuts : 342 0: 1 30 1: 1 150 3: 1 225 4: 1 135 5: 1 160 6: 1 80 9: 1 90 10: 1 100 11: 1 120 Total weight: 1090 Total Value: 9 Total Steps: 3526 Total Cuts : 342 0: 1 30 1: 1 150 3: 1 225 4: 1 135 5: 1 160 6: 1 80 9: 1 90 10: 1 100 11: 1 120 Total weight: 1090 1 2 3 4 5 6 7 8 9 10
11 12 13 1100 12 1 30 1 150 1 305 1 225 1 135 1 160 1 80 1 200 1 165 1 90 1 100 1 120

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---