【正经题解】秒杀双十一
2024-02-22 10:27:36
发布于:浙江
2阅读
0回复
0点赞
#include<iostream>
using namespace std;
const int MAX_N = 100001;
const int MAX_M = 900001;
int dp[MAX_M]; // dp数组用于存储状态转移的结果
int w[MAX_N]; // w数组用于存储商品价格
int c[MAX_N]; // c数组用于存储商品重要度
int num[MAX_N]; // num数组用于存储每种商品最大购买数量
int main() {
int n, m, sum;
cin >> m >> n;
// 输入商品信息
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i] >> sum;
if (sum == 0) {
num[i] = m / w[i];
} else {
num[i] = min(sum, m / w[i]);
}
}
// 动态规划
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= num[i]; k++) {
for (int j = m; j >= 0; j--) {
if (j >= w[i]) {
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
}
}
}
}
// 输出结果
cout << dp[m];
return 0;
}
这里空空如也
有帮助,赞一个