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