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

ops/2025/3/7 2:32:31/

文章目录

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

前言

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

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

一、例题

在这里插入图片描述

二、分析题意

其实这就是一个完全背包问题，每个物品可以无限次数的拿取，当然，一个纯的完全背包问题问的是一个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;
}