蓝桥省赛 包子凑数 完全背包

这篇具有很好参考价值的文章主要介绍了蓝桥省赛 包子凑数 完全背包。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍑 算法题解专栏


🍑 洛谷 P8646 包子凑数

[蓝桥杯 2017 省 AB] 包子凑数

题目描述

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N N N 种蒸笼,其中第 i i i 种蒸笼恰好能放 A i A_i Ai 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

每当有顾客想买 X X X 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X X X 个包子。比如一共有 3 3 3 种蒸笼,分别能放 3 3 3 4 4 4 5 5 5 个包子。当顾客想买 11 11 11 个包子时,大叔就会选 2 2 2 3 3 3 个的再加 1 1 1 5 5 5 个的(也可能选出 1 1 1 3 3 3 个的再加 2 2 2 4 4 4 个的)。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 3 3 种蒸笼,分别能放 4 4 4 5 5 5 6 6 6 个包子。而顾客想买 7 7 7 个包子时,大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入格式

第一行包含一个整数 N N N ( 1 ≤ N ≤ 100 ) (1 \le N \le 100) (1N100)

以下 N N N 行每行包含一个整数 A i A_i Ai ( 1 ≤ A i ≤ 100 ) (1 \le A_i \le 100) (1Ai100)

输出格式

一个整数代表答案。如果凑不出的数目有无限多个,输出 INF

样例 #1

样例输入 #1

2  
4  
5

样例输出 #1

6

样例 #2

样例输入 #2

2  
4  
6

样例输出 #2

INF

提示

对于样例 1 1 1,凑不出的数目包括: 1 , 2 , 3 , 6 , 7 , 11 1,2,3,6,7,11 1,2,3,6,7,11

对于样例 2 2 2,所有奇数都凑不出来,所以有无限多个。

蓝桥杯 2017 省赛 A 组 H 题。


🍑 思路
🍁 裴蜀定理:当 gcd(a,b) == 1 时,这两个数最大不能凑出来的数是:(a-1)(b-1)-1
🍁 数据最大取到 100,最大的两个互质数 为 100 和 99,那 最大不能凑出的数 小于 98*99

🍑 完全背包二维版

import java.util.*;

public class Main
{
	static int N = 110, M = 10010;
	static int[] a = new int[N];
	static boolean[][] f = new boolean[N][M];

	static int gcd(int a, int b)
	{
		return b == 0 ? a : gcd(b, a % b);
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int d = 0;// 任何数 和 0 的最大公约数都是 它本身
		for (int i = 1; i <= n; i++)
		{
			a[i] = sc.nextInt();
			d = gcd(d, a[i]);
		}
		if (d != 1)
			System.out.println("INF");
		else
		{
			f[0][0] = true;

			for (int i = 1; i <= n; i++)
				for (int j = 0; j < M; j++)
				{
					f[i][j] = f[i - 1][j];
					if(j >= a[i])
						f[i][j] |= f[i][j-a[i]];
				}
			
			int res = 0;
			for(int i = 0; i < M; i++)
			{
				if(!f[n][i])
					res++;
			}
			System.out.println(res);
		}
	}
}

🍑 滚动数组优化版文章来源地址https://www.toymoban.com/news/detail-426033.html

import java.util.Scanner;

public class Main
{
	static int N = 110, M = 10010;
	static int[] a = new int[N];
	static boolean[] f = new boolean[M];

	static int gcd(int a, int b)
	{
		return b == 0 ? a : gcd(b, a % b);
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int d = 0;// 任何数 和 0 的最大公约数都是 它本身
		for (int i = 1; i <= n; i++)
		{
			a[i] = sc.nextInt();
			d = gcd(d, a[i]);
		}
		if (d != 1)
			System.out.println("INF");
		else
		{
			f[0] = true;

			for (int i = 1; i <= n; i++)
				for (int j = a[i]; j < M; j++)
				{
					f[j] |= f[j - a[i]];
				}

			int res = 0;
			for (int i = 0; i < M; i++)
			{
				if (!f[i])
					res++;
			}
			System.out.println(res);
		}
	}
}

到了这里,关于蓝桥省赛 包子凑数 完全背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 背包问题——01背包|完全背包

    目录 前言背包问题的历史  01背包  1、题目 2、暴力解01背包  Ⅰ、代码 3、动态规划解01背包 Ⅰ、二维dp数组解01背包 1)dp数组的含义  2)递推公式  3)dp数组的初始化  4)遍历顺序的讨论  5、代码  Ⅱ、一维数组解01背包  1)一维数组|滚动数组  2)一维数组的含义及递

    2024年02月02日
    浏览(45)
  • 【动态规划之完全背包问题】完全背包问题的通用解法与优化

    ⭐️ 前面的话 ⭐️ 本篇文章将介绍动态规划中的背包问题——完全背包问题,前面我们已经介绍了0-1背包问题,其实完全背包问题就只改了0-1背包问题的一个条件,即物品可选择次数由一次改为无数次,仅此而已,下面我们就来开始介绍完全背包问题。 📒博客主页:未见

    2023年04月22日
    浏览(47)
  • 动态规划-背包问题-完全背包

    对比01背包,完全背包中的每件物品有无数件。 也就是说,每件物品可以拿0,1,…,k,…件。 dp[i][j]表示前i种物品,体积为j时的最大价值 对于第i件物品: 不拿:dp[i][j]⇐dp[i-1][j] 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i] 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i] … 拿k件:dp[i]][j]⇐dp[i

    2024年04月08日
    浏览(46)
  • 背包问题分析代码详解【01背包+完全背包+多重背包】

    一、01背包问题 问题描述: 有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。 朴素01背包 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值 状态转移 1) 选第i个物品:f[i,j] = f

    2024年02月06日
    浏览(37)
  • 动态规划之背包问题——完全背包

    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)——动态规划 2 数组 算法分析之数组问题 3 链表 算法

    2024年02月03日
    浏览(53)
  • 动态规划——01背包和完全背包

    目录 01背包模型 题目  dp   滚动数组优化 第一问  第二问  扩展 完全背包 题目  动态规划​编辑  滚动数组优化  关于-1的代码层面优化 💰🪙 背包就是有限制条件的组合问题 有一个背包能容纳的体积是v,现在有n个物品,第i个物品的体积为vi,价值为wi。 (1)求这个背包

    2024年01月20日
    浏览(39)
  • 完全背包&多重背包问题(动态规划)

    完全背包问题: 每个物品使用次数没有限制,与0-1背包的不同之处在于 遍历背包的顺序 是正序。 多重背包问题: 与完全背包的区别在于,每一种物品是有个数限制的,不能无限选择。这篇博客讲解的非常详细,可以参考学习: 多重背包问题---超详细讲解+优化(不懂你揍我

    2024年04月10日
    浏览(46)
  • 背包~~~~~~~~~3478:【例86.3】 完全背包问题

    【题目描述】 设有n�种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M�,今从n�种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M�,而价值的和为最大。 【输入】 第一行:两个整数,M�(背包

    2024年01月18日
    浏览(32)
  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(49)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包