当前位置:首页 > 洛谷 > 洛谷P1616题解:动态规划之完全背包问题

洛谷P1616题解:动态规划之完全背包问题

2个月前 (07-14)

洛谷P1616题解:动态规划之完全背包问题 洛谷题解 动态规划 完全背包问题 C++ 第1张

一、题目解读

洛谷P1616题要求在一个包含M个活动(每个活动有固定时间和价值)的场景中,求解在总时间T内选择活动的最优组合,使得总价值最大化。活动可重复选择,需利用动态规划算法找到最优解。题目强调时间限制与价值收益的平衡,属于典型的完全背包问题变体。

二、解题思路

1. 动态规划核心思想:将问题拆解为子问题,通过状态转移方程逐步求解全局最优解。

2. 完全背包模型:与01背包不同,完全背包允许每个物品(活动)被选择多次,因此状态转移需考虑重复选择的可能性。

3. 优化策略:使用一维DP数组(空间优化),通过正序遍历容量(时间)实现状态更新,避免重复计算。

三、解题步骤

1. 数据输入与初始化:

○ 读取总时间T和活动数量M。

○ 使用vector存储每个活动的时间time和价值value。

○ 初始化DP数组dp,其中dp[j]表示在时间j内可获得的最高价值。

2. 动态规划循环:

○ 外层遍历活动(物品),内层正序遍历时间(容量)。

○ 状态转移方程:dp[j] = max(dp[j], dp[j - time[i]] + value[i]),即当前时间j的价值可选择“不选该活动”或“选该活动并扣除其时间后剩余价值+当前价值”。

3. 输出结果:dp数组的最后一个元素dp[t]即为最优解。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t, m;  // t为总时间,m为活动数量
    cin >> t >> m;
    
    vector<int> time(m), value(m);  // time存储活动时间,value存储活动价值
    for (int i = 0; i < m; ++i) {
        cin >> time[i] >> value[i];
    }
    
    vector<long long> dp(t + 1, 0);  // dp[i]表示前i时间内的最大价值,初始化为0
    
    // 完全背包核心算法
    for (int i = 0; i < m; ++i) {  // 遍历每个活动
        for (int j = time[i]; j <= t; ++j) {  // 正序遍历时间(容量)
            dp[j] = max(dp[j], dp[j - time[i]] + value[i]);  // 状态转移:选择当前活动或不选择
        }
    }
    
    cout << dp[t] << endl;  // 输出最终结果
    return 0;
}

五、总结

本文通过动态规划方法解决了洛谷P1616题中的时间价值优化问题,利用完全背包模型允许重复选择的特点,通过简洁的状态转移方程实现了高效求解。代码采用一维DP数组降低空间复杂度,正序遍历确保重复选择的有效性。该解法为同类背包问题提供了通用框架,需重点理解状态定义与转移逻辑,适用于资源可重复利用的最优决策场景。


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣70题:告别暴力递归!从零实现记忆化搜索解法

力扣70题:告别暴力递归!从零实现记忆化搜索解法

题意解析:想象你站在楼梯底部,面前有n级台阶。每次你可以选择跨1级或2级台阶,最终到达顶端的路径有多少种不同的走法?这个问题本质上是在探索分叉决策的叠加效果——当我们把每个台阶处的选择看作二叉树的分支...

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

力扣145:递归之美 轻松掌握二叉树后序遍历

力扣145:递归之美 轻松掌握二叉树后序遍历

题目解读二叉树的后序遍历是一种基础且重要的树遍历方式,其遍历顺序为:先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。这种遍历方式特别适合需要先处理子节点再处理父节点的场景,如内存释放...

力扣540题:线性扫描法如何高效定位唯一数

力扣540题:线性扫描法如何高效定位唯一数

题目重解一个严格递增的有序数组中,除某个元素外,其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间...

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。