AtCoder Regular Contest 042 C: おやつ

問題

arc042.contest.atcoder.jp

解法

最も安い1個については0円と見なすことが出来ると考える。

商品を値段の降順でソートして高い方から見ていき、動的計画法で「高い方からn個目までみた時の、予算内での最大の幸福度」を求める。n+1個め以降から最も幸福度の高いものを選んでそこに加えることができ、この最後の1個は金額を考える必要がない。nを0からNまで回して最大値を求めれば良い。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int P = scanner.nextInt();
		Snack[] snacks = new Snack[N];
		for (int i = 0; i < N; i++) {
			snacks[i] = new Snack(scanner.nextInt(), scanner.nextInt());
		}
		scanner.close();
		Arrays.sort(snacks);

		// dp[n][p]:= n個目まで考えた時にp円での最大の満足度
		int[][] dp = new int[N + 1][P + 1];
		for (int i = 0; i <= N; i++) {
			Arrays.fill(dp[i], -1);
		}
		for (int i = 0; i <= N; i++) {
			dp[i][0] = 0;
		}

		for (int i = 0; i < N; i++) {
			for (int p = 0; p < P; p++) {
				if (dp[i][p] < 0) {
					continue;
				}
				dp[i + 1][p] = Math.max(dp[i][p], dp[i + 1][p]);
				if (p + snacks[i].cost > P) {
					continue;
				}
				dp[i + 1][p + snacks[i].cost] = Math.max(dp[i + 1][p
						+ snacks[i].cost], dp[i][p] + snacks[i].value);
			}
		}

		int max = 0;
		for (int n = 1; n <= N; n++) {
			int dpMax = 0;// n個目までで考えた時の予算内の最大の満足度
			for (int p = 0; p <= P; p++) {
				dpMax = Math.max(dpMax, dp[n][p]);
			}

			int lastMax = 0;// n個目以降で最大の満足度
			for (int i = n; i < N; i++) {
				lastMax = Math.max(lastMax, snacks[i].value);
			}

			max = Math.max(max, dpMax + lastMax);
		}
		System.out.println(max);

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

class Snack implements Comparable<Snack> {
	int cost, value;

	public Snack(int a, int b) {
		this.cost = a;
		this.value = b;
	}

	@Override
	public int compareTo(Snack o) {
		return o.cost - this.cost;
	}

}