蓝桥杯每日一题01背包拔高·小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();
}