Algorithm Problem: Loading problem

A large ship is to be loaded with containers of cargos. Different containers, although of equal size, will have different weights.

Let wi be the weight of the i th container, 1 ? i ? n, and the capacity of the ship is c, we want to find out a way to load the ship with the maximum number of containers, without tipping over the ship.

Let xi ? {0, 1}. If xi = 1, we will load the i th container, otherwise, we will not load it.

We wish to assign values to xi s such that Pn i=1 xiwi ? c, and Pn i=1 xi is maximized.

Goal: Come up with a solution as how we should load into the ship