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

蓝桥杯每日一题01背包拔高·小A点菜

P1164 小A点菜

题意: 有M大的背包, N种物品, 每种物品价值为1, 体积为 a ,求方案数。

题解: 背包五大分析模块, 确定下标含义, 初始化数组, 推出递推公式, 输出答案, 我用一维01背包那么j就代表背包题解M, 那么

  • 当j的值等于a时候 : dp[j] = max(dp[j], dp[j - a] + 1 )
  • 当j的值大于a时候 : dp[j] = dp[j] + dp[j - a];
  • 当j的值小于a时候: 不变 dp[j] = dp[j];

对于第二点我这里做出解释:
当前菜品方案数加上加上种类为i体积为a的菜品的方案数,这样就能叠加总方案数

AC Code

// Problem: P1164 小A点菜
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1164
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
typedef long long ll; // 确保 ll 在使用前被定义
using namespace std;
using i64 = long long;
using u64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= m;++i)
#define int long long 
#define pii pair<int,int>
#define In \
		ll n; \
		std::cin >> n;\

const int mod = 1e8, N = 1005;

int dp[N];

// 一维dp


// 01 背包底层原理究竟是什么?
void solve() {
	int n, m;std::cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		int a;std::cin >> a;
		for(int j = m; j >= 0; --j) {
			if(j == a) {
				dp[j] = dp[j] + 1;
			} else if(j > a) {
				dp[j] = dp[j] + dp[j - a];
			} 
		}
	}
	std::cout << dp[m] << "\n";
}


signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); std::cout.tie(0);
	ll T = 1;
	//std::cin >> T;
	for(int i = 1; i <= T; ++i) solve();
}

http://www.kler.cn/a/587860.html

相关文章:

  • Navicat SqlServer 设置自增主键
  • 【人工智能】大语言模型学习大纲
  • 使用 Django 的 `FileResponse` 实现文件下载与在线预览
  • 【虚幻C++笔记】枚举UENUM、结构体USTRUCT
  • 基于CPU使用paddlex OCR识别图片内容
  • 《 线程池项目:线程池背景知识与整体架构梳理》
  • Postman中Authorization和Headers的区别
  • 【软考网工-实践篇】DHCP 动态主机配置协议
  • 【Vue列表渲染中key与数据绑定的核心问题解析】
  • 小程序渲染之谜:如何解决“加载中...”不消失的 Bug(glass-easel)
  • SpringMVC (二)请求处理
  • docker Mysql主从配置
  • 【设计模式】《设计模式:可复用面向对象软件的基础》:设计模式怎样解决设计问题?
  • Vue 系列之:ref、reactive、toRef、toRefs
  • 合并pull request的过程
  • 色彩重生:基于 Retinex 理论的 UR2P-Dehaze 去雾增强器解析
  • PyTorch 深度学习实战(13):Proximal Policy Optimization (PPO) 算法
  • 面试常见概念区分:并发与并行、同步与异步、阻塞与非阻塞、线程同步与互斥
  • 设计模式之装饰器模式:原理、实现与应用
  • 阿里云服务器购买及环境搭建宝塔部署springboot和vue项目