Java實作 藍橋杯VIP 算法提高 貪吃的大嘴

算法提高 貪吃的大嘴

時間限制：1.0s 記憶體限制：256.0MB

問題描述

　　有一隻特别貪吃的大嘴,她很喜歡吃一種小蛋糕,而每一個小蛋糕有一個美味度,而大嘴是很傲嬌的,一定要吃美味度和剛好為m的小蛋糕,而且大嘴還特别懶,她希望通過吃數量最少的小蛋糕達到這個目的.是以她希望你能設計一個程式幫她決定要吃哪些小蛋糕.

輸入格式

　　先輸入一行包含2個整數m、n,表示大嘴需要吃美味度和為m的小蛋糕,而小蛋糕一共有n種,下面輸入n行,每行2個整數,第一個表示該種小蛋糕的美味度,第二個表示蛋糕店中該種小蛋糕的總數

輸出格式

　　輸出一行包含一個整數表示大嘴最少需要吃的小蛋糕數量,若大嘴無法通過吃小蛋糕達到m的美味度和,則輸出"><“.

樣例輸入

10 2

4 1

2 10

樣例輸出

4

樣例輸入

10 2

4 1

7 3

樣例輸出

<

資料規模和約定

　　m ≤ 20000,小蛋糕總數量≤50.

import java.util.Scanner;


public class 貪吃的大嘴 {
	public static void main(String[] args){
		int[] val = new int[51];//蛋糕的價值
		int[] num = new int[51];//蛋糕的數量
		int[] dp = new int[20005];//dp數組，dp[i]表示吃美味度為i的蛋糕最小要吃多少種
		//輸入資料
		Scanner sc = new Scanner(System.in);
		String[] s1 = sc.nextLine().split(" ");
		int m = Integer.parseInt(s1[0]);//美味度
		int n = Integer.parseInt(s1[1]);//蛋糕種類
		
		for(int i=1;i<=n;i++)
		{
			String[] s2 = sc.nextLine().split(" ");
			val[i] = Integer.parseInt(s2[0]);
			num[i] = Integer.parseInt(s2[1]);
		}
		//初始化dp,
		int inf = 99999999;
		for(int i = 1;i<=m;i++)
			dp[i] = inf;
		dp[0] = 0;
		//dp過程
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=num[i];j++)
				for(int k = m;k>=val[i];k--)
					dp[k] = Math.min(dp[k-val[i]]+1, dp[k]);
		
		
		if(dp[m] == inf)
			System.out.println("><");
		else
			System.out.println(dp[m]);
		
	}

}