蓝桥杯算法提高VIP-贪吃的大嘴 （Java代码）

package com.dotcpp.question;

import java.util.Scanner;

/**
 * 贪吃的大嘴(重复背包问题)
 * @author Mikoto
 *
 */
public class Test1566 {
	private static int m,n;
	private static int [] ns;//蛋糕甜度和数量
	private static int [] ca;//索引和蛋糕甜度
	public static void main(String[] args) {
		ns = new int[20000];//创建数组
		ca = new int[20000];
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		for(int i=0;i<n;i++) {
			int sw = sc.nextInt();
			int nu = sc.nextInt();
			ns[sw] = nu;
			ca[i] = sw;
		}
		dp();
	}
	public static void dp() {
		int [][] dp = new int[n+1][m+1];//n表示物品，m表示甜度		
		for(int j=0;j<dp[0].length;j++) {//0个蛋糕，除0甜度外任何甜度都不能凑齐
			dp[0][j] = -1;
		}
		for(int i=0;i<dp.length;i++) {//0个甜度时，任何情况都只需要0个蛋糕
			dp[i][0]=0;
		}
		for (int i = 1; i < dp.length; i++) {
			int num = ns[ca[i-1]];
			for (int j = 1; j < dp[i].length; j++) {				
				int b = 20000;//用于比较最佳方案
				for(int k=0;k<=num;k++) {
					int ms = k*ca[i-1];//k个甜品的甜度
					if(j>=ms&&dp[i-1][j-ms]!=-1) {//当前甜度小于需要甜度，并且所需要子集可以凑齐
						int c = dp[i-1][j-ms]+k; //状态转移方程
						b = b<c?b:c;//可以满足且需要蛋糕最少
					}	
				}			
				if(b!=20000)//能否凑齐需要甜度
					dp[i][j] = b;//给dp数组赋值
				else
					dp[i][j] =-1;//无法凑齐甜度赋值为-1
			}
		}
		if(dp[n][m]!=-1) {			
			System.out.println(dp[n][m]);
		}else {
			System.out.println("><");
		}
		/*for(int i=0;i<dp.length;i++) {
			System.out.println(Arrays.toString(dp[i]));
		}*/

	}
}

解题思路 背包问题（动态规划）

注意事项:蛋糕=价值，甜度=权重