#179129 (Java21) No.527 ナップサック容量問題

• 問題: No.527 ナップサック容量問題
• ユーザー: schwarzahl
• 提出日時: 2017-06-10 01:56:21
• 言語: Java21 (openjdk 21)
• 結果: WA
• 実行時間: -
• コード長: 2,128 bytes
• コンパイル時間: 2,764 ms
• コンパイル使用メモリ: 80,252 KB
• 実行使用メモリ: 74,652 KB
• 最終ジャッジ日時: 2023-10-24 04:50:30
• 合計ジャッジ時間: 13,796 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	145 ms; 61,808 KB
testcase_01	AC	144 ms; 61,620 KB
testcase_02	AC	151 ms; 61,852 KB
testcase_03	AC	146 ms; 59,740 KB
testcase_04	AC	147 ms; 61,832 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	148 ms; 61,716 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	144 ms; 61,708 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	148 ms; 61,776 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	AC	192 ms; 61,804 KB
testcase_25	AC	161 ms; 61,800 KB
testcase_26	AC	214 ms; 63,868 KB
testcase_27	AC	202 ms; 62,024 KB
testcase_28	AC	155 ms; 61,780 KB
testcase_29	AC	248 ms; 64,292 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	147 ms; 61,860 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-

ソースコード

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

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

	private void solveA() {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int h = c2i(line.charAt(0)) * 10 + c2i(line.charAt(1));
		int m = c2i(line.charAt(3)) * 10 + c2i(line.charAt(4));
		m += 5;
		if (m >= 60) {
			m -= 60;
			h += 1;
			h = h % 24;
		}
		System.out.printf("%02d:%02d", h, m);
	}

	private int c2i(char c) {
		return c - '0';
	}

	private void solveB() {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long M = sc.nextLong();

		long pp = 0;
		long p = 1;
		for (int n = 3; n <= N; n++) {
			long now = (pp + p) % M;
			pp = p;
			p = now;
		}
		System.out.println(p);
	}

	private void solveC() {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		List<Budget> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			Budget b = new Budget();
			b.v = sc.nextInt();
			b.w = sc.nextInt();
			list.add(b);
		}
		int V = sc.nextInt();

		int MAX_W = 1000001;
		int[] values = new int[MAX_W];

		Set<Integer> set = new HashSet<>();
		set.add(0);
		for (Budget b : list) {
			Set<Integer> next_set = new HashSet<>();
			for (int weight : set) {
				int tmp_v = values[weight];
				int next_v = tmp_v + b.v;
				int next_w = weight + b.w;
				if (next_w < MAX_W && next_v > values[next_w]) {
					values[next_w] = next_v;
					if (next_v <= V) {
						next_set.add(next_w);
					}
				}
				next_set.add(weight);
			}
			set = next_set;
		}
		int min = 1;
		Integer max = null;
		for (int wi = 0; wi < MAX_W; wi++) {
			if (min == 1 && V > 0 && values[wi] == V) {
				min = wi;
			}
			if (max == null && values[wi] > V) {
				max = wi;
			}
		}
		System.out.println(min);
		System.out.println(max == null ? "inf" : max - 1);
	}

	class Budget {
		int v;
		int w;

		public int getValue() {
			return v;
		}

		public int getWeight() {
			return w;
		}
	}
}