今日のエントリーも Java8 ネタです。
このところ Java8 のエントリーがほとんどになってきたけど Lambda をはじめ、新機能がよく理解できてないので慣れることを目標としてます。(^_^;)
今回は無理矢理 Java8 を使って有名なナップサック問題を解くプログラムを創ってみました。
それでは下記のようなデータの人たちがいるとします。
<– Person –>
柴田 恭平, 61歳, Gender: MALE 体重 : 70 評価 : 8
壇 蜜, 32歳, Gender: FEMALE 体重 : 60 評価 : 6
北川 景子, 26歳, Gender: FEMALE 体重 : 55 評価 : 7
綾瀬 はるか, 28歳, Gender: FEMALE 体重 : 50 評価 : 4
佐々木 希, 25歳, Gender: FEMALE 体重 : 48 評価 : 9
剛力 彩芽, 20歳, Gender: FEMALE 体重 : 45 評価 : 6
小栗 旬, 30歳, Gender: MALE 体重 : 65 評価 : 3
堀北 真希, 24歳, Gender: FEMALE 体重 : 45 評価 : 10
武井 咲, 19歳, Gender: FEMALE 体重 : 50 評価 : 5
市原 隼人, 26歳, Gender: MALE 体重 : 67 評価 : 2
深田 恭子, 30歳, Gender: FEMALE 体重 : 50 評価 : 8
あなたはヨットをもっていてクルージングを楽しもうとしています。
上記の人たちが「是非ご一緒させてください」と申し出てきました。
ヨットの制限であと 180 キログラムまでしか乗船できません。
そこであなたは、女性を同伴させることにします。
重量制限のあるなか、あなたは女性の評価値の総和が最大になるように同伴メンバーを選ばなくてはなりません。
今回はヨットであり、希望者も少ないのでわざわざプログラムを組む必要はないでしょう。
しかし、ある日突然大金持ちになって豪華客船でクルージングなんてことがあるかもしれません。（ヲヒ
プログラムの内容は 0-1 ナップサック問題 動的計画法アルゴリズムで良く知られているから解説はしません。
Java8 だとこんな風に組めるのかくらいに斜めにみてください。
package jp.yucchi.dp4lambda;
import java.time.LocalDate;
import java.time.Period;
public class Person {
public enum Sex {
MALE, FEMALE
}
String firstName;
String lastName;
LocalDate birthday;
Sex gender;
int weight;
int evaluation;
public Person(String firstName, String lastName, LocalDate birthday, Sex gender, int weight, int evaluation) {
this.firstName = firstName;
this.lastName = lastName;
this.birthday = birthday;
this.gender = gender;
this.weight = weight;
this.evaluation = evaluation;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public Sex getGender() {
return gender;
}
public int getAge() {
return Period.between(birthday, LocalDate.now()).getYears();
}
void printPerson() {
System.out.println(firstName + " " + lastName + ", " + this.getAge() + "歳" + ", Gender: "
+ this.getGender() + " 体重 : " + this.getWeight() + " 評価 : " + this.getEvaluation());
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getEvaluation() {
return evaluation;
}
public void setEvaluation(int evaluation) {
this.evaluation = evaluation;
}
}
package jp.yucchi.dp4lambda;
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class DP4Lambda {
public static void main(String[] args) {
List person = new ArrayList<>();
person.add(new Person("柴田", "恭平", LocalDate.of(1951, 8, 18), Person.Sex.MALE, 70, 8));
person.add(new Person("壇", "蜜", LocalDate.of(1980, 12, 3), Person.Sex.FEMALE, 60, 6));
person.add(new Person("北川", "景子", LocalDate.of(1986, 8, 22), Person.Sex.FEMALE, 55, 7));
person.add(new Person("綾瀬", "はるか", LocalDate.of(1985, 3, 24), Person.Sex.FEMALE, 50, 4));
person.add(new Person("佐々木", "希", LocalDate.of(1988, 2, 8), Person.Sex.FEMALE, 48, 9));
person.add(new Person("剛力", "彩芽", LocalDate.of(1992, 8, 27), Person.Sex.FEMALE, 45, 6));
person.add(new Person("小栗", "旬", LocalDate.of(1982, 12, 26), Person.Sex.MALE, 65, 3));
person.add(new Person("堀北", "真希", LocalDate.of(1988, 10, 6), Person.Sex.FEMALE, 45, 10));
person.add(new Person("武井", "咲", LocalDate.of(1993, 12, 25), Person.Sex.FEMALE, 50, 5));
person.add(new Person("市原", "隼人", LocalDate.of(1987, 2, 6), Person.Sex.MALE, 67, 2));
person.add(new Person("深田", "恭子", LocalDate.of(1982, 11, 2), Person.Sex.FEMALE, 50, 8));
int maxW = 180;
int[] pw = person.parallelStream()
.filter(e -> e.getGender() == Person.Sex.FEMALE)
.mapToInt(p -> p.getWeight()).toArray();
int[] pv = person.parallelStream()
.filter(e -> e.getGender() == Person.Sex.FEMALE)
.mapToInt(p -> p.getEvaluation()).toArray();
int[][] dp = new int[pw.length + 1][maxW + 1];
IntStream.range(0, pw.length).forEach(i -> {
IntStream.rangeClosed(0, maxW).forEach(j -> {
if (j < pw[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - pw[i]] + pv[i]);
}
});
});
System.out.println("合計評価 : " + dp[pw.length][maxW]);
boolean[] isChoice = new boolean[pw.length];
int mW = maxW;
for (int i = pw.length - 1; i >= 0; i--) {
if (pw[i] <= mW && dp[i][mW] < dp[i][mW - pw[i]] + pv[i]) {
isChoice[i] = true;
mW -= pw[i];
}
}
IntStream.range(0, isChoice.length).forEach(e -> {
if (isChoice[e]) {
// Optional 使用
Optional p = person.parallelStream().filter(k -> k.getGender() == Person.Sex.FEMALE).substream(e, e + 1).findFirst();
if (p.isPresent()) {
p.get().printPerson();
} else {
System.out.println("エラー発生！ （×_×）");
}
// Person 使用
// Person pp = person.parallelStream().filter(k -> k.getGender() == Person.Sex.FEMALE).collect(Collectors.toList()).get(e);
// pp.printPerson();
}
});
}
}
実行結果は下記のようになります。
合計評価 : 27
佐々木 希 年齢 : 25 Gender : FEMALE 体重 : 48 評価 : 9
堀北 真希 年齢 : 24 Gender : FEMALE 体重 : 45 評価 : 10
深田 恭子 年齢 : 30 Gender : FEMALE 体重 : 50 評価 : 8
間違っているかもしれません。そのときは優しくご指摘くださいませ。
Java8 に詳しい方は「ここはこうすれば良いのにとかあればコソッとコメント入れといてくれると嬉しいです。」 なんてね。(^_^)
＊注意＊ 2013年7月2日 API 使用変更に対応、ついでに選んだ人の情報取得方法を Optional と Person を使う二種類記述しました。
