c++背包问题（随取随用）
2026-08-24 11:30:51
发布于：浙江
22阅读
0回复
0点赞
直接上混合
表示完全背包， 表示 背包，否则多重背包
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void yz();
signed main() {
// freopen("xxx.in", "r", stdin); freopen("xxx.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) yz();
}
struct node {
int w, c;
};
const int N = ______;
const int M = ______;
int m, n, w[N], c[N], s[N];
long long dp[M];
void yz() {
memset(dp, 0, sizeof dp);
cin >> m >> n;
// cout << m << " " << n << endl;
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> c[i] >> s[i];
// cout << w[i] << " " << c[i] << " " << s[i] << endl;
}
for (int i = 1; i <= n; ++i) {
if (s[i] == 1) {
// 01 背包，从大到小
for (int j = m; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
} else if (s[i] == 0) {
// 完全背包，从小到大
for (int j = w[i]; j <= m; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
} else {
// 多重背包，二进制优化转 01 背包求解
int num = s[i];
for (int cur = 1; num >= cur; cur <<= 1) {
int ww = cur * w[i], cc = cur * c[i];
for (int j = m; j >= ww; --j)
dp[j] = max(dp[j - ww] + cc, dp[j]);
num -= cur;
}
if (num) {
int ww = num * w[i], cc = num * c[i];
for (int j = m; j >= ww; --j)
dp[j] = max(dp[j - ww] + cc, dp[j]);
}
}
}
cout << dp[m] << endl;
}
有帮助，赞一个