NO.87十六届蓝桥杯备战|动态规划-完全背包|疯狂的采药|Buying Hay|纪念品(C++)

最新推荐文章于 2025-05-19 23:16:24 发布

ChoSeitaku

最新推荐文章于 2025-05-19 23:16:24 发布

阅读量955

点赞数 18

分类专栏：蓝桥杯备考文章标签：蓝桥杯动态规划 c++

本文链接：https://blog.csdn.net/CoderZzz6310/article/details/147126763

版权

蓝桥杯备考专栏收录该内容

157 篇文章

订阅专栏

完全背包

先解决第⼀问

状态表⽰：
dp[i][j]表⽰：从前i个物品中挑选，总体积不超过j，所有的选法中，能挑选出来的最⼤价
值。（这⾥是和01背包⼀样哒）
那我们的最终结果就是dp[n][V] 。
状态转移⽅程：
线性dp状态转移⽅程分析⽅式，⼀般都是根据最后⼀步的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：
a. 选0个第i个物品：此时相当于就是去前i-1个物品中挑选，总体积不超过j。此时最⼤价值为dp[i - 1][j]；
b. 选1个第i个物品：此时相当于就是去前i-1个物品中挑选，总体积不超过j-v[i]。因为挑选了⼀个i物品，此时最⼤价值为dp[i-1][j-v[i]]+w[i]；
c. 选2个第i个物品：此时相当于就是去前o-1个物品中挑选，总体积不超过j-2 x v[i]。因为挑选了两个i物品，此时最⼤价值为dp[i-1][j - 2 v[i]] + 2 * w[i]；
综上，状态转移⽅程为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 × v[i]] + 2 × w[i]...
当计算⼀个状态的时候，需要⼀个循环才能搞定的时候，就要想到去优化。优化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态，通常就是⽤数学的⽅式做⼀下等价替换。
观察发现第⼆维是有规律的变化的，因此去看看dp[i][j - v[i]]这个状态：
dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 × v[i]] + w[i], dp[i - 1][j - 3 × v[i]] + 2 × w[i]...)
我们发现，把dp[i][j - v[i]]加上w[i]正好和dp[i][j]中除了第⼀项以外的全部⼀致，因们可以修改状态转移⽅程为：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
初始化：
我们多加⼀⾏，⽅便我们的初始化，此时仅需将第⼀⾏初始化为0即可。因为什么也不选，也能满⾜体积不⼩于j的情况，此时的价值为0。
填表顺序：
根据状态转移⽅程，我们仅需从上往下填表即可。

接下来解决第⼆问：
第⼆问仅需修改⼀下初始化以及最终结果即可。

初始化：
因为有可能凑不⻬j体积的物品，因此我们把不合法的状态设置为负⽆穷。这样在取最⼤值的时候，就不会考虑到这个位置的值。负⽆穷⼀般设置为-0x3f3f3f3f即可。
然后把dp[0][0]修改成0，因为这是⼀个合法的状态，最⼤价值是0，也让后续填表是正确
的。
返回值：
在最后拿结果的时候，也要判断⼀下最后⼀个位置是不是⼩于0 ，因为有可能凑不⻬
不能判断是否等于-0x3f3f3f3f，因为这个位置的值会被更新，只不过之前的值太⼩，导致更新后还是⼩于0的。

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

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    //第一问
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    
    //第二问
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    }
    if (f[n][m] < 0) cout << 0 << endl;
    else cout << f[n][m] << endl;
    
    return 0;
}

空间优化

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

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    //第一问
    for (int i = 1; i <= n; i++)
    {
        for (int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    
    //第二问
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    if (f[m] < 0) cout << 0 << endl;
    else cout << f[m] << endl;
    
    return 0;
}

P2918 [USACO08NOV] Buying Hay S - 洛谷

完全背包模版题。

状态表⽰：
dp[i][j] 表⽰：从前i 个药材中挑选，总时间不超过j ，此时能采摘到的最⼤价值。
那么dp[n][m]就是结果。
状态转移⽅程：
对于i 位置的药材，可以选择采0, 1, 2, 3… 个：
a. 选0 个：最⼤价值为dp[i - 1][j] ；
b. 选1 个：最⼤价值为dp[i - 1][j - t[i]] + v[i] ；
c. 选2 个：最⼤价值为dp[i - 1][j - 2 × t[i]] + 2 × v[i] ；
d. …
由于要的是最⼤价值，应该是上述所有情况的最⼤值。其中第⼆个往后的状态可以⽤dp[i][j - t[i]] + v[i]替代，因此状态转移⽅程为
dp[i][j] = max(dp[i - 1][j], dp[i][j - t[i]] + v[i])
初始化：
全部初始化0 ，不影响后续填表的正确性。
填表顺序：
从上往下每⼀⾏，每⼀⾏从左往右。
空间优化版本也是如此

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

typedef long long LL;

const int N = 1e4 + 10, M = 1e7 + 10;

int n, m;
int t[N], w[N];
LL f[M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> t[i] >> w[i];

    for (int i = 1; i <= n; i++)
    {
        for (int j = t[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j-t[i]]+w[i]);       
        }
    }
    cout << f[m] << endl;
    
    return 0;
}

P2918 [USACO08NOV] Buying Hay S - 洛谷

完全背包简单变形。

状态表⽰：
dp[i][j]表⽰：从前i 个⼲草公司中挑选，总重量⾄少为j 磅，此时的最⼩开销。
注意注意注意！这是我们遇到的第三类限制情况。
之前的限制条件为不超过j ，或者是恰好等于j 。这道题的限定条件是⾄少为j ，也就是说可以超过j。这会对我们分析状态转移⽅程的时候造成影响。
根据状态表⽰，dp[n][m] 就是结果。
状态转移⽅程：
对于i 位置的公司，可以选择买0, 1, 2, 3… 个：
a. 选0 个：开销为dp[i - 1][j] ；
b. 选1个：开销为dp[i - 1][j - p[i]]+c[i] 。问题来了，状态表⽰⾥⾯是⾄少为j ，也就是说j - p[i]⼩于0也是合法的。因为公司提供了p[i]的重量，⼤于j，是符合要求的。但是dp表的下标不能是负数，处理这种情况的⽅式就是对j-p[i]与0取⼀个最⼤值。当重量很⼤的时，只⽤去前⾯凑重量为0的就⾜够了，这样就符合我们的状态表⽰了。因此，最终开销为
dp[i - 1][max(0, j - p[i])] + c[i]
c. 选2 个：开销为dp[i - 1][max(0, j - 2 × p[i])] + 2 × c[i] ；
d. …
由于要的是最⼩开销，应该是上述所有情况的最⼩值。
其中第⼆个往后的状态可以⽤dp[i][max(0, j - p[i])] + c[i] 替代，因此状态转移⽅程为dp[i][j] = min(dp[i - 1][j], dp[i][max(0, j - p[i])] + c[i])
初始化：
全部初始化正⽆穷⼤0x3f3f3f3f ，然后dp[0][0] = 0 ，不影响后续填表的正确性。
填表顺序：
从上往下每⼀⾏，每⼀⾏从左往右。
空间优化版本也是如此

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

const int N = 110, M = 50010;

int n, m;
int p[N], c[N];
int f[N][M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> p[i] >> c[i];

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = min(f[i-1][j], f[i][max(0, j-p[i])] + c[i]);        
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}

空间优化

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

const int N = 110, M = 50010;

int n, m;
int p[N], c[N];
int f[M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> p[i] >> c[i];

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[j] = min(f[j], f[max(0, j-p[i])] + c[i]);        
        }
    }
    cout << f[m] << endl;
    
    return 0;
}

P5662 [CSP-J2019] 纪念品 - 洛谷

总策略：贪⼼。从前往后，⼀天⼀天的考虑如何最⼤⾦币。
因为纪念品可以在当天买，当天卖。因此所有的交易情况，就可以转换成"某天买隔天卖"的情况。那么，我们就可以贪⼼的将每⼀天能拿到的最⼤利润全都拿到⼿：

从第⼀天开始，把第⼀天的⾦币看成限制条件，第⼆天的⾦币看成价值，求出：在不超过m的情况下，能获得的最⼤价值m1；
然后时间来到第⼆天，把这⼀天的⾦币看成限制条件，第三天的⾦币看成价值，求出：在不超m1的情况下，能获得的最⼤价值m2；
以此类推，直到把第t - 1天的情况计算出来，能获得最⼤价值就是结果。
接下来就处理，拿到第i⾏以及i+1⾏数据，在最⼤⾦币数量为m的前提下，获得的最⼤利润是
多少？
因为每⼀个纪念品都可以⽆限次购买；
把前⼀⾏看成限制，后⼀⾏减去前⼀⾏的值看成价值，就变成了标准的完全背包问题。
那我们的解决⽅法就是⼀⾏⼀⾏的跑完全背包，跑⼀⾏拿到最⼤价值，然后放到下⼀⾏继续跑，直到跑完倒数第⼆⾏。
完全背包的逻辑：

状态表⽰：
dp[i][j]表⽰从前i 个纪念品中挑选，总花费不超过j 的情况下，最⼤的利润。
那么，dp[n][m] + m就是能得到的最⼤⾦币数量
状态转移⽅程：
根据最后⼀个纪念品选的数量，分成如下情况：
a. 如果选0 个：能获得的最⼤⾦币数量为dp[i - 1][j] ；
b. 如果选1 个：能获得的最⼤⾦币数量为dp[i - 1][j - w[i]] + v[i] - w[i] ；
c. 如果选2 个：能获得的最⼤⾦币数量为dp[i - 1][j - 2 × w[i]] + 2 × (v[i] - w[i])
d. …
其中除了第⼀个状态外的所有状态都可以⽤dp[i][j - w[i]] + v[i] - w[i] 来表⽰，⼜因为要的是最⼤值，所以状态转移⽅程就是所有情况的最⼤值。
初始化
全为0 即可

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

const int N = 110, M = 1e4 + 10;

int t, n, m;
int p[N][N];
int f[M];

//完全背包
int solve(int v[], int w[], int m)
{
    //清空数据
    memset(f, 0, sizeof f);

    for (int i = 1; i <= n; i++)
    {
        for (int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j-v[i]] + w[i] - v[i]);        
        }
    }
    
    return f[m] + m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t >> n >> m;
    for (int i = 1; i <= t; i++)
        for (int j = 1; j <= n; j++)
            cin >> p[i][j];

    //贪心
    for (int i = 1; i < t; i++)
    {
        m = solve(p[i], p[i+1], m);       
    }

    cout << m << endl;
    
    return 0;
}