目录

蓝桥-动态规划-倒水

JAY.LIN 收录于算法我一生之敌

2025-03-14 约 618 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146265576

目录

【蓝桥】-动态规划-倒水

一、问题描述

二、解题思路

一个 变种的01背包问题：
不选该物品 ：获得固定收益 e
选择方案1 ：消耗体积 a ，获得价值 b
选择方案2 ：消耗体积 c ，获得价值 d
目标是在背包容量 m 的限制下，最大化总收益。

三、完整代码

二维dp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1010;
ll dp[N][N]; // dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
ll n, m, a, b, c, d, e;

int main() {
    cin >> n >> m; // 输入物品数量 n 和背包容量 m

    for (int i = 1; i <= n; i++) {  // 遍历每个物品
        cin >> a >> b >> c >> d >> e;
        
        for (int j = 0; j <= m; j++) { 
            // 不选当前物品，继承上一个状态
            dp[i][j] = dp[i - 1][j] + e;  

            // 选方案1（需要容量 >= a）
            if (j >= a) 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b);

            // 选方案2（需要容量 >= c）
            if (j >= c) 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + d);
        }
    }

    cout << dp[n][m] << '\n'; // 输出最大价值
    return 0;
}

使用滚动数组

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
ll dp[N], n, m, a, b, c, d, e;
int main(){
  cin >> n >> m;  // 输入物品数量n和背包容量m
  while(n -- ){   // 遍历每个物品
    cin >> a >> b >> c >> d >> e;  // 输入物品参数
    for(int i = m; i >= 0; -- i) { // 逆向遍历背包容量
      // 处理三种决策
      if(i >= a) 
        dp[i] = max(dp[i] + e, dp[i - a] + b); // 方案1 vs 不选
      if(i >= c) 
        dp[i] = max(dp[i], dp[i - c] + d);     // 方案2 vs 当前最优
      if(i < a) 
        dp[i] = dp[i] + e;                     // 无法选方案1，只能不选
    }
  }
  cout << dp[m] << '\n';  // 输出结果
  return 0;
}

关键逻辑说明

逆向遍历背包容量
使用 for(int i = m; i >= 0; -- i) 确保每个物品只被处理一次 （类似01背包优化） 。
三种决策的优先级

方案1优先 ：先尝试选择体积 a 的方案，更新 dp[i] 。
方案2次优先 ：再尝试选择体积 c 的方案，与当前最优值比较。
强制不选 ：当 i < a 时，强制加上不选收益 e 。