■ 貪欲法(greedy algorithm)
* greedy（グリーディ） = 貪欲な、欲張り、食いしん坊
* 評価値(= 価値 / 重量) が高い品物を選ぶ
貪欲法の特徴
* 必ずしも正しい解が得られるとは限らない
=> 正しい解に近い値(近似値)を得られる
手順
1) それぞれの品物の評価値を計算する
2) 評価値を高い順にソートする
3) 評価値の高い順から組み合わせを耐荷重を超えないように試していく
サンプル
package com.dk.jenkins;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GreedyAlgorithm {
private static final int MaxWeightForKnapsack = 6;
public static void main(String[] args) {
GreedyAlgorithm greedyAlgorithm = new GreedyAlgorithm();
List<Item> items = new ArrayList<Item>();
items.add(greedyAlgorithm.new Item("A", 100, 1));
items.add(greedyAlgorithm.new Item("B", 300, 2));
items.add(greedyAlgorithm.new Item("C", 350, 3));
items.add(greedyAlgorithm.new Item("D", 500, 4));
items.add(greedyAlgorithm.new Item("E", 650, 5));
Collections.sort(items);
greedyAlgorithm.greedy(items);
}
public void greedy(List<Item> items) {
int restWeight = MaxWeightForKnapsack;
int totalPrice = 0;
int totalWeight = 0;
for (Item item : items) {
if (restWeight >= item.getItemWeight()) {
System.out.println("Item ID : " + item.itemId);
totalPrice = totalPrice + item.itemPrice;
totalWeight = totalWeight + item.itemWeight;
restWeight = restWeight - item.itemWeight;
}
}
System.out.println("Total Price : " + totalPrice);
System.out.println("Total Weight : " + totalWeight);
}
class Item implements Comparable<Item> {
private String itemId;
private int itemPrice;
private int itemWeight;
public Item(String itemId, int itemPrice, int itemWeight) {
this.itemId = itemId;
this.itemPrice = itemPrice;
this.itemWeight = itemWeight;
}
public String getItemId() {
return this.itemId;
}
public int getItemPrice() {
return this.itemPrice;
}
public int getItemWeight() {
return this.itemWeight;
}
public int getEvaluationValue() {
return this.itemPrice / this.itemWeight;
}
@Override
public int compareTo(Item comparedItem) {
return comparedItem.getEvaluationValue() - this.getEvaluationValue();
}
}
}
出力結果
Item ID : B
Item ID : D
Total Price : 800
Total Weight : 6
