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