当前位置：首页 > article >正文

动态规划之 “完全背包“ ------P8646 [蓝桥杯 2017 省 AB] 包子凑数

article 2025/3/6 2:53:24

文章目录

前言
一、例题
二、分析题意
三、代码示例
总结

前言

今天讲一道蓝桥真题
需要的前置知识点是完全背包，如果对此知识点不懂可以点击此处了解代码随想录之完全背包

现在我们有了这个前置知识点后直接开始看题

一、例题

在这里插入图片描述

二、分析题意

其实这就是一个完全背包问题，每个物品可以无限次数的拿取，当然，一个纯的完全背包问题问的是一个j容量的背包在对于一些物品无限次拿取的时候最大价值为多少，这道题我们要求的不是最大价值，而是背包是否可以被装满，比如我的背包容量为5，如果dp[5]=5说明可以被装满，按照题目的意思就是可以凑出5这个数

那什么时候是INF无限个数呢？其实我们开数据范围就能知道，我们只需要开一个较大的dp数组即可

dp状态转移公式
dp[j]=max(dp[j],dp[j-value[i]]+value[i])
我们在求完全背包的问题，在遍历背包的时候一定是正序遍历的，因为一件物品可以多次拿取，如果这里还有疑惑，说明前置知识点并没有理解透彻，请点击前言部分的链接学习完01背包一维dp和完全背包问题后再解决此题目

三、代码示例

#include<iostream>
using namespace std;
int n;
int value[110];
int dp[1000005];//背包容量为i能装的最大价值为dp[i]
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>value[i];
	}
	
	for(int i=1;i<=n;i++)//遍历物品
	{
		for(int j=value[i];j<=1000000;j++)//正序遍历背包 因为一件物品可以被多次拿取
		{
			dp[j]=max(dp[j],dp[j-value[i]]+value[i]);
		}
	}
	
	int ans=0;
	for(int i=1;i<=1000000;i++)
	{
		if(dp[i]==0||dp[i]!=i)
		{
			ans++;//记录凑不出数的个数
		}
	}
	
	if(ans>=500000)cout<<"INF";//如果有500000个数凑不出 那基本上就是无限了
	else
	{
		cout<<ans;//否则直接输出多少个数不可以被凑出
	}
	return 0;
}