复兴提高DAY03背包问题
2025-07-03 20:20:48
发布于：上海
34阅读
0回复
0点赞
T1小码君的01背包
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值
int main() {
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
// 当前背包容量装不进第i个物品，则价值等于前i-1个物品
if(j < v[i])
f[i][j] = f[i - 1][j];
// 能装，需进行决策是否选择第i个物品
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
T2采药
#include<bits/stdc++.h>
using namespace std;
const int T=1005,M=105;
int dp[M][T],m,t,c[M],w[M];
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++)
cin>>c[i]>>w[i];
for(int i=1;i<=m;i++){
for(int j=1;j<=t;j++){
if(j>=c[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[m][t];
return 0;
}
T3小码君的01背包(优化)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[30005];
int w[10005], v[10005];
int main()
{
int c, n;
cin >> c >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = c; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[c] << '\n';
return 0;
}
T4装箱问题
#include<iostream>
using namespace std;
int a[20010]; // 存储每个物品的体积
int f[20010]; // 存储动态规划的结果
int main(){
int x, n;
cin >> x >> n; // 输入箱子容量和物品数量
for(int i = 1; i <= n; i++){
cin >> a[i]; // 输入每个物品的体积
}
for(int i = 1; i <= n; i++){
for(int j = x; j >= 1; j--){
if(j >= a[i]){
f[j] = max(f[j], f[j - a[i]] + a[i]); // 动态规划更新结果
}
}
}
cout << x - f[x] << endl; // 输出最小空间
return 0;
}
T5[NOIP2006 普及组] 开心的金明
#include <iostream>
using namespace std;
int f[30][100000];
int w[10000];
int v[10000];
int main()
{
int n,m;
int i,j,k;
cin>>m>>n;
//提前相乘
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
v[i]*=w[i];
}
for(int i=1;i<=n;i++)
{
//01背包最关键的位置,为防止反复加同一物品，需要倒着搜，这也是01背包与完全背包的不同之处
for(int c=0;c<=m;c++)
{
f[i][c]=f[i-1][c];
if(c>=w[i])
f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
}
}
cout<<f[n][m];
return 0;
}
T6疯狂的采药
#include<bits/stdc++.h>
using namespace std;
int dp[35][1005];
int w[1005];
int v[1005];
int main(){
int n,m;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m];
return 0;
}
T7交易
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
long long dp[N];
int a[N],b[N],c[N];
int main() {
int m,k;
cin>>m;
for(int i=1;i<=m;i++) {
cin>>a[i]>>b[i]>>c[i];
}
cin>>k;
for(int i=1;i<=m;i++) {
for(int j=b[i];j<=k;j++){
dp[j]=max(dp[j],dp[j-b[i]]+c[i]);
}
}
cout<<dp[k]<<endl;
return 0;
}
T8神奇的魔法币
//状态定义：dp[i][j]：使用前 i 种魔法币，总价值为 j 的情况下，实现愿望的不同支付方式数量。
//
//策略选择：
//
//对于每种魔法币 a[i]，我们可以选择使用或不使用它来实现愿望。
//
//状态转移：
//
//如果当前考虑的魔法币面值 a[i] 小于等于总价值j，则可以选择使用该魔法币。在这种情况下，支付方式数量 dp[i][j] 等于两部分的和：
//
//不使用魔法币 a[i] 时，即前 i?1 个魔法币实现总价值为 j 的支付方式数量，即 dp[i?1][j]。
//
//使用魔法币 a[i] 时，即前i个魔法币实现总价值为 j?a[i] 的支付方式数量，即 dp[i][j?a[i]] 在加上不使用这种魔法币的支付方式数量 dp[i?1][j]。
//
//如果当前考虑的魔法币面值 a[i] 大于总价值 j ，则无法使用该魔法币来实现总价值为 j ，因此支付方式数量dp[i][j] 等于前 i?1 种魔法币实现总价值为j的支付方式数量，即 dp[i?1][j] 。
//
//得到状态转方程 dp[i][j]=dp[i?1][j]+dp[i][j?a[i]]
//
//最后的答案即为 dp[n][m]，表示使用所有 n 种魔法币，实现总价值为 m 的不同支付方式数量。
#include <bits/stdc++.h>
using namespace std;
long long m, n, dp[110][3010], a[110];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
if (j >= a[i])
dp[i][j] = dp[i - 1][j] + dp[i][j - a[i]];
else
dp[i][j] = dp[i - 1][j];
}
cout << dp[n][m];
return 0;
}
T9多重背包
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,v,c[N*N],w[N*N],dp[N];
int x,y,z,cnt;
int main(){
cin>>v>>n;
for(int i=1;i<=n;i++){
cin>>x>>y>>z;//物品的体积、价值、数量
for(int j=1;j<=z;j++){
cnt++;
c[cnt]=x;
w[cnt]=y;
}
}
for(int i=1;i<=cnt;i++){
for(int j=v;j>=c[i];j--){
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
cout<<dp[v];
return 0;
}
T10多重背包升级版
#include <iostream>
#include <vector>
using namespace std;
long long n,m;
long long f[1000005];
struct Good{
long long v, w;
};
vector<Good>goods;
int main(){
cin >> m >> n;
for (int i = 1; i <= n; i++){
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2) {
s -= k;
goods.push_back({ k * v,k * w });
}
if(s > 0) goods.push_back({ s * v,s * w });
}
for (int it=0;it<goods.size();it++){
for (int j = m; j >= goods[it].v; j--) {
f[j] = max(f[j], f[j - goods[it].v] + goods[it].w);
}
}
cout << f[m] << endl;
return 0;
}
T11分组背包
//由于每组中最多选择一个，对物品进行分组。定义 dp[i][j] 表示考虑前 i 组物品，
//背包容量为 j 时获得的最大价值，状态转移方程为 dp[i][j]=max(dp[i][j],dp[i-1][j-w]+c)。
//枚举每组物品需要放到最内层循环，这样每一个背包容量 j 才是被每组的一个物品更新，即每组最多选一个。
#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;
}
T12分组背包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;
}
T13小码君需要你的帮助
//分析题目可以发现，每门课花费的时间只有一种可能，这其实时分组背包。定义 dp[i][j]
// 表示考虑前 i 门课，有的时间为 j 时获得的最大价值，状态转移方程为 dp[i][j]=max(dp[i][j],dp[i-1][j-w]+c)。
#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;
}
这里空空如也
有帮助，赞一个