In a container terminal, export containers are usually classified into one of a few weight groups and those belonging to the same group are stored together on a same stack. The reason for this stacking by weight groups is that it becomes easy to have heavier containers be loaded onto a ship before lighter ones, which is important for the balancing of the ship. However, since the weight information available at the time of container arrival is only an estimate, containers belonging to different weight groups are often stored together on a same stack. This becomes the cause of extra moves, or re-handlings, of containers at the time of loading to fetch out the heavier containers placed under the lighter ones. In this paper, we propose a method based on a simulated annealing search to derive a good stacking strategy for containers with uncertain weight information. Simulation experiments have shown that our strategies more effectively reduce the number of re-handlings than the traditional same-weight-group-stacking strategy. Also, additional experiments have shown that further improvement can be obtained if we increase the accuracy of the weight classification by applying machine learning.