蓝桥杯算法训练VIP-邮票 （Java代码）

解题思路:

类似背包问题



注意事项:


活动结束，没能提交测试。


参考代码:

import java.util.Scanner;

/** 
* @ClassName: A 
* @Description: TODO(这里用一句话描述这个类的作用) 
* @author J-King
* @date 2018年3月22日 下午2:39:38 
*  
*/
public class Main
{
        //可贴邮票的最大数量
	static int maxNum ;
	//邮票种类
	static int type ;
	//可通过贴canCal[i]张邮票达到i面额
	static int[] canCal ;
	//邮票的面额
	static int [] size ;
	
	public static void input() {
		
		Scanner scanner = new Scanner(System.in);
		maxNum = scanner.nextInt();
		type = scanner.nextInt();
		
		size = new int[type]; 
		canCal = new int[10010];
		
		for(int i = 0 ; i < type ; i ++)
			size[i] = scanner.nextInt();
		scanner.close() ;
	}
	
	public static int solve(){
		for(int  j = 0 ; j < type ; j++){
			//一张邮票即可
			canCal[size[j]] = 1 ;
			for(int i = 1 ; i+ size[j] <= 10000 ; i ++){
				if(canCal[i] > 0 && canCal[i] < maxNum){
					if(canCal[i + size[j]] != 0 && canCal[i + size[j]] < canCal[i] + 1)
						continue;
					canCal[i + size[j]] = canCal[i] + 1 ;
					
				}
			}
		}
		
		for(int i = 1 ; i <= 10000 ; i ++){
			if(canCal[i] == 0 )
				return i-1 ;
		}
		
		return 0 ;
	}
	
	
	public static void main(String[] args) {
		input();
		System.out.println(solve());;
	}
	
}