algorithmmathcapacity-planning

Calculating truck cargo capacity in a game


This is more of a math/algorithm question than a programming question, but I hope you guys can help anyway.

Scenario #1:

Player 1 has 40 crates in his inventory.

Player 1 has 2 trucks,

1x small (capacity: 8 crates)

1x medium (capacity: 16 crates)


Given capacity:

A small truck can hold 8 crates

A medium truck can hold 16 crates

A large truck can hold 30 crates

How many trucks does player 1 need to be able to take all 40 crates?

Scenario #2, what happens if there is cargo already in trucks?

Player 1 has 40 crates and 2 trucks as above scenario.

If small already has 2 crates in its load, giving him 8-2 = 6 space

If medium already has 4 crates in its load, giving him 16-4 = 8 space

How many trucks does player 1 need to take all 40 crates? What would the algorithm be?

Scenario #3: No trucks

Player 1 has 0 trucks at all. How many trucks does he need to take all 40 crates? Again, what is the algoritm you would use?

Scenario #4: Too many trucks

Player 1 has 10 trucks, all at large capacity. How many trucks does it take to ship all 40 crates?

I'm thinking.

Scenario 1,

2 trucks, 1 small = 8 and 1 medium = 16
8+16 = 24 crates
40 - 24 = 16 trucks?? // This looks wrong.

Costs of trucks are done earlier on (you buy them first).

I think my algorithm is wrong. Do I need to divide it by a base number? Do I divide it by trucks?

Any help on this would be very helpful.


Solution

  • I suggest the following algorithm (in pseudocode)

    do truck = 1,number_trucks
      current_capacity(truck) = total_capacity(truck) - loaded_crates(truck)
    enddo
    sort trucks according to current_capacity (biggest first)
    remaining_crates = 40
    do truck = 1,number_trucks
      if(remaining_crates - current_capacity(truck) > 0)
        load truck full
        remaining_crates -= current_capacity(truck)
      else
        if(truck != last truck)
          if(remaining_crates - current_capacity(truck+1) > 0)
            load truck with remaining_crates
            remaining_crates = 0
          endif
        else
          load truck full
          remaining_crates -= current_capacity(truck)
        endif
      endif
    enddo
    sort truck_class according to total_capacity(truck_class) (biggest first)
    do truck_class = 1,number_truck_classes
      while(remaining_crates - total_capacity(truck_class) > 0)
        buy truck of truck_class
        remaining_crates -= total_capacity(truck_class)
      end while
      if(truck_class == number_truck_classes && remaining_crates > 0)
        buy truck of truck_class
      endif
    enddo