01背包问题合集 蓝桥OJ

一、蓝桥OJ 1174小明的背包1 模板题

思路：

用二维数组dp判断最大价值，i表示物品数量，j表示物品体积，如果 j > V 则无需继续， j >= w 物品还能再增加，同样价值也增加，否则继承之前的价值，在之间找Max，最大价值。

#include<bits/stdc++.h>
using namespace std;const int N = 1e3 + 4;
int dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin >> n >> V;for(int i = 1; i <= n; i++){int w, v; cin >> w >> v;for (int j = 1; j <= V; j++){if (j >= w)dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);else dp[i][j] = dp[i-1][j];}}cout << dp[n][V] << '\n';return 0;
}

优化思路：

避免新数据更新为新数据。上面的代码每次j的下标都是从小到大， 故可以直接当作一个数组，每次更新时，从后往前更新。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 4;
int dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin >> n >> V;for (int i = 1; i <= n; i++){int w, v;cin >> w >> v;for (int j = V; j >= w; j--){dp[j] = max(dp[j], dp[j-w]+v);}}cout << dp[V] << '\n';return 0;
}

二、蓝桥OJ 2223背包与魔法

思路：

这道题可以分成三类，1.不选 2.选但不用魔法 3.选且用魔法， 三种中取最大价值的。 

#include<bits/stdc++.h>
using namespace std;const int N = 1e4+5;
int dp[N][2]; // 0的时候表示魔法已用,1表示魔法没用int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m, k; cin >> n >> m >> k;for (int i = 1; i <= n; i++){int w, v; cin >> w >> v;for (int j = m; j >= 0; --j){if (j >= w){dp[j][0] = max(dp[j][0],dp[j-w][0]+v);dp[j][1] = max(dp[j][1],dp[j-w][1]+v);}if (j >= w + k){dp[j][1] = max(dp[j][1], dp[j-w-k][0]+2*v);}}}cout << max(dp[m][0], dp[m][1]) << '\n';return 0;
}

三、蓝桥OJ 3741倒水

思路：

用一个二维dp数组记录所有满意度之和的最大值，dp[i][j]中的i表示1~i个客人，j表示 倒水j毫升。

分3种情况，是否倒着写要看情况：

1.当j < a时，dp[i][j] = dp[i-1][j]+e

2.当j >= a and j < c时， dp[i][j] = max(dp[i-1][j]+e, dp[i-1][j-a]+b)

3.当j>=c时， dp[i][j] = max(dp[i-1][j-c]+d , max(dp[i-1][j]+e, dp[i-1][j-a]+b))

下面的代码第一次写忘记了开long long！！！一定要记住 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 8;
ll dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){int a, b, c, d, e;cin >> a >> b >> c >> d >> e;for (int j = 0; j <= m; j++){if (j < a) dp[i][j] = dp[i-1][j]+e;else if (j >= a && j < c) dp[i][j] = max(dp[i-1][j]+e,dp[i-1][j-a]+b);else if (j >= c) dp[i][j] = max(dp[i-1][j-c]+d, max(dp[i-1][j]+e,dp[i-1][j-a]+b));}}cout << dp[n][m] << '\n';return 0;
}

 四、蓝桥OJ 3637盗墓分赃2

尽量把数组开大一点，不然会有测试点错误。

思路：

01背包的变形，宝藏的重量即宝藏的价值，当宝藏的重量和为奇数，一定不能平均的分成两份。后面跟01背包一样

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 8;
int a[N],dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin >> n;int sum = 0;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}if (sum&1){cout << "no" << '\n';return 0;}sum = sum / 2;for (int i = 1; i <= n; i++){for (int j = sum; j >= a[i]; j--){dp[j] = max(dp[j],dp[j-a[i]]+a[i]);}}string res = (dp[sum] == sum) ? "yes": "no";cout << res << '\n';return 0;
}

五、蓝桥OJ 5118小兰的神秘礼物

跟 盗墓分赃 一模一样 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 8;
int x[N], dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int V; cin >> V;//箱子的容量int n; cin >> n;//收集的小物件总数for (int i = 1; i <= n; i++) cin >> x[i];for (int i = 1; i <= n; i++)for (int j = V; j >= x[i]; j--) dp[j] = max(dp[j],dp[j-x[i]]+x[i]);cout << V-dp[V] << '\n';return 0;
}