CODEWITHSUNDEEP
c++
user3088184
user3088184

Reputation: 41

How many runs are needed?

A person can carry 'x' kg. That person must move 'y' items of different weights. If multiple items can be combined and carried in one go, how many runs are needed?

Here's what I think the beginning of code should look:

#include "Item.h"
using namespace std;


int main()
{
  Item A[10];
  int t; 
  string name1; int weight1;
  ifstream read("File.txt");
  read >> t;
    for (int i = 0; i < t; i++){
      read >> name1 >> weight1;
      A[i].Set(name1, weight1);
    }
  read.close();
  //find maximum weight item:
  int r = 0;
    for (int i = 0; i < t; i++){
     if (A[i].GetWeight() > A[r].GetWeight())
     r = i;
    }
     int maxItemWeight = A[r].GetWeight();
     cout << A[r].GetWeight();

    int carryWeight = 100; //How much weight a person can carry at once
    int times; // Times to carry all the items

    if (maxItemWeight > carryWeight)
        cout << "It's impossible to carry all the items " << endl;
    else {
          //Any advice for this part????
     }


    cout << "Times to carry all the items: " << times << endl;
    return 0;
  }

Upvotes: 2

Views: 125

Answers (2)

David Hammen
David Hammen

Reputation: 33126

Suppose you start by putting items into bins, each of which can contain 60 kg at most. Once you've placed all of the items into bins you know exactly how many trips are needed. Simply count the number of bins used.

Here's a lousy algorithm: Put an item into the first bin into which it will fit. It's O(n), so it's fast. Suppose your array contains six 10 kg items and then six 50 kg items. This algorithm will place those first six 10 kg items in one bin, filling it to capacity. The remaining six items have to go in separate bins, so seven bins overall. If you had simply attacked the problem from the other end you would have found the optimal solution of six bins, and hence six trips. This algorithm can at times overstate the number of bins by a factors of two.

Sorting helps, but it does not guarantee optimality. Any polynomial time algorithm can overstate the number of bins needed by 22%. Sorting is the key to reaching that 22% figure. An optimal solution has to exhaust all possible arrangements. You can use backtracking to accomplish this. On the other hand, an O(n*log(n)) algorithm that comes within 22% of optimal might well be good enough.

If you google "bin packing problem" you will find a lot of literature on this problem because this problem has lots of industrial applications.

Upvotes: 4

John Dibling
John Dibling

Reputation: 101476

I might start by picking up the heaviest item first. Then find the next heaviest item you can pick up. Continue searching until you can't pick up any more items. Save that configuration.

Drop everything but the first item. Find the 2nd heaviest item you can pick up. Continue searching until you can't pick up any more.

Keep looping like this, saving each configuration, and then actually carry the configuration with the most number of packages. If there is a tie, carry the combination with the heaviest single item.

I don't claim this is optimal, but I think it should work.

Upvotes: 1

Related Questions