复兴提高班第二十课 分组背包
2025-10-19 19:25:08
发布于：上海
15阅读
0回复
0点赞
T1分组背包
#include<bits/stdc++.h>
using namespace std;
int dp[19][209];
struct node {
int w, c;
};
vector<node> ve[19];
int main() {
int V, N, T;
cin >> V >> N >> T;
for (int i = 0; i < N; i++) {
int W, C, P;
cin >> W >> C >> P;
ve[P].push_back({ W,C });
}
for (int i = 1; i <= T; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i - 1][j];//不拿物品
for (int k = 0; k < ve[i].size(); k++) {
if (j >= ve[i][k].w) dp[i][j] = max(dp[i][j], dp[i - 1][j - ve[i][k].w] + ve[i][k].c);
}
}
}
cout << dp[T][V];
return 0;
}
T2分组背包2
#include<bits/stdc++.h>
using namespace std;
int dp[2009];
struct node {
int w, c;
};
vector<node> ve[100009];
int main() {
int V, N, T;
cin >> V >> N >> T;
for (int i = 0; i < N; i++) {
int W, C, P;
cin >> W >> C >> P;
ve[P].push_back({ W,C });
}
for (int i = 1; i <= T; i++) {
if (ve[i].size() == 0) continue;
for (int j = V; j >= 0; j--) {
for (int k = 0; k < ve[i].size(); k++) {
if (j >= ve[i][k].w) dp[j] = max(dp[j], dp[j - ve[i][k].w] + ve[i][k].c);
}
}
}
cout << dp[V];
return 0;
}
T3小码君需要你的帮助
#include<bits/stdc++.h>
using namespace std;
int dp[109], a[109][109];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
for (int j = 0; j <= m; j++) dp[j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 1; k <= m; k++) {
if (j >= k) dp[j] = max(dp[j], dp[j - k] + a[i][k]);
}
}
}
cout << dp[m] << '\n';
return 0;
}
T4通天之分组背包
#include<bits/stdc++.h>
using namespace std;
struct node {
int w, c;
};
long long dp[1009];
vector<node> ve[109];
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
ve[c].push_back({ a,b });
}
for (int i = 1; i <= 100; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 0; k < ve[i].size(); k++) {
if (j >= ve[i][k].w) dp[j] = max(dp[j], dp[j - ve[i][k].w] + ve[i][k].c);
}
}
}
cout << dp[m];
return 0;
}
T5我爱运动鞋
#include<bits/stdc++.h>
using namespace std;
int dp[19][10009];
struct node {
int w, c;
};
vector<node> ve[19];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i <= 10; i++) ve[i].clear();
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
ve[a].push_back({ b,c });
}
memset(dp, -1, sizeof(dp));
for (int i = 0; i <= m; i++) dp[0][i] = 0;
for (int i = 1; i <= k; i++) {
for (int z = 0; z < ve[i].size(); z++) {
for (int j = m; j >= ve[i][z].w; j--) {
if (dp[i][j - ve[i][z].w] != -1) {
dp[i][j] = max(dp[i][j], dp[i][j - ve[i][z].w] + ve[i][z].c);
}
if (dp[i - 1][j - ve[i][z].w] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - ve[i][z].w] + ve[i][z].c);
}
}
}
}
if (dp[k][m] == -1) cout << "Impossible" << '\n';
else cout << dp[k][m] << '\n';
return 0;
}
有帮助，赞一个