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.

回答1:

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

回答2:

It's very helpful when you're trying to work out this sort of thing to keep the units

40 crates - 24 crates = 16 crates

The player has 40 crates, he has the ability to transport 24 crates, so he needs additional trucks to transport the remaining crates. The most efficient way, presumably, to transport 16 crates would be with 1 additional medium truck (you could also get 1 large truck or 2 small trucks).