マウント問題-欲張りアルゴリズム

既存の1つの荷重Wの貨物船、コンテナi個、重量はそれぞれwiであり、体積を考慮せずに積載数が最も多いことが要求されている.
これは,01リュックのような単純な最適積載問題であるが,価値ではなく数量を考慮しているので,残りのコンテナの中で最も軽量なものを選択するたびに,貪欲なアルゴリズムにより最適解を得ることができる.

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by saishangmingzhu on 2018/11/30.
 */
public class BinPackingProblem {
    public static void main(String[] arg) {
        new BinPackingProblem().greedy();
    }

    /**
     *     
     */
    public void greedy(){
        int rucksackWeight=10;
        List goodsList=new ArrayList<>();
        goodsList.add(1);
        goodsList.add(3);
        goodsList.add(7);
        goodsList.add(3);
        goodsList.add(1);
        goodsList.add(5);
        goodsList.add(4);
        Collections.sort(goodsList);
        int surplus=rucksackWeight;
        List resultGoodsList=new ArrayList<>();
        for (Integer goods:goodsList){
            if (surplus>=goods.intValue()){
                surplus=surplus-goods.intValue();
                resultGoodsList.add(goods);
            }
        }
        System.out.println(resultGoodsList.size());
    }
}