動的計画法をJavaでメモ化再帰で記述してみた。

以下のナップザック問題をメモ化再帰で記述してみました。
https://atcoder.jp/contests/dp/tasks/dp_d

残念ながら、0_00, 0_01, 0_02, 1_00, 1_01, はACでしたが、他がTLEになってしまいました。

こちらの記事を見て今度はforループで解いてみたいと思います。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2

Main.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {

            var numberOfItem = sc.nextLong();
            var maxWeight = sc.nextLong();

            List<Goods> goods = new ArrayList<>();
            for (int i = 0; i < numberOfItem; i++) {
                goods.add(new Main().new Goods(sc.nextLong(), sc.nextLong()));
            }

            System.out.println(dp(goods, 0, maxWeight, 0L, 0L, new HashMap<>()));
        }

    }

    public static Long dp(List<Goods> goods, Integer goodsIndex, Long maxWeight, Long nowValue, Long nowWeight,
            Map<DpMemo, Long> memos) {

        if (memos.containsKey(new Main().new DpMemo(goodsIndex, nowWeight, nowValue))) {
            // すでに計算済みのときはメモから値を取得する。
            return memos.get(new Main().new DpMemo(goodsIndex, nowWeight, nowValue));
        }

        Long maxValue = 0L;
        if (goodsIndex >= goods.size()) {
            maxValue = nowValue;
        } else if (nowWeight + goods.get(goodsIndex).getWeight() <= maxWeight) {
            // 重さの最大値を超えないときは、goodsを入れる場合と、入れない場合の両方を計算し、最大値を取得する。
            maxValue = Math.max(dp(goods, goodsIndex + 1, maxWeight, nowValue + goods.get(goodsIndex).getValue(),
                    nowWeight + goods.get(goodsIndex).getWeight(), memos),
                    dp(goods, goodsIndex + 1, maxWeight,
                            nowValue, nowWeight, memos));
        } else {
            // 重さの最大値を超えたときは、goodsを入れない。
            maxValue = dp(goods, goodsIndex + 1, maxWeight,
                    nowValue, nowWeight, memos);
        }
        memos.put(new Main().new DpMemo(goodsIndex, nowWeight, nowValue), maxValue);
        return maxValue;
    }

    public class Goods {

        private final Long weight;

        private final Long value;

        public Goods(Long weight, Long value) {
            this.weight = weight;
            this.value = value;
        }

        public Long getWeight() {
            return weight;
        }

        public Long getValue() {
            return value;
        }

    }

    public class DpMemo {

        private final Integer index;

        private final Long weight;

        private final Long value;

        public DpMemo(Integer index, Long weight, Long value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public Integer getIindex() {
            return index;
        }

        public Long getWeight() {
            return weight;
        }

        public Long getValue() {
            return value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(index, weight, value);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            DpMemo other = (DpMemo) obj;
            return Objects.equals(index, other.index) && Objects.equals(weight, other.weight)
                    && Objects.equals(value, other.value);
        }
    }
}