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;
}