DP(2)--背包DP(0-1 背包,完全背包,多重背包)

news/2024/10/30 11:29:17/

滚动数组: 让数组滚动起来,每次都使用固定的几个存储空间,来达到压缩,节省存储空间的作用。
一般用于递推和动态规划中

一维数组
比如:求斐波那契数列第100项
long long arr[3];
arr[0] = 1;
arr[0] = 1;
for (int i = 2; i < 100; ++i)
    arr[i%3] = arr[(i-1)%3] + arr[(i-2)%3];

二维数组
int dp[1000][1000];
for (int i = 1; i < 1000; ++i)
    for (int j = 0; j < 1000; ++j)
        dp[i][j] = dp[i-1][j] + dp[i][j-1];

运用滚动数组
int dp[2][1000];
for (int i = 1; i < 1000; ++i)
    for (int j = 0; j < 1000; ++j)
        dp[i%2][j] = dp[(i-1)%2][j] + dp[i%2][j-1];
        
0-1 背包
有n个物品和一个容量为c的背包,每个物品有重量w[i]和v[i]两种属性,
选取若干个物品放入背包使背包中的物品总价值最大且背包中物品的总重量不超过背包的容量。
设DP状态f[i][j]为在前i个物品中选取,容量为j的背包所能达到的最大价值
状态转移: 假设当前已经处理好了前i-1个物品的所有状态,
那么对于第i个物品,当其不放入背包时,背包的剩余容量不变,背包中物品的总价值也不变,故这种情况的最大价值为f[i-1][j];
当其放入背包时,背包的剩余容量会减小w[i],背包中物品的总价值会增大 v[i],故这种情况的最大价值为 f[i-1][j-w[i]]+v[i].
由此可以得出状态转移方程:
    f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i])
由于对f[i]有影响的只有f[i-1],可以去掉第一维,直接用f[i]表示处理到当前物品时背包容量为i的最大价值
 
洛谷 2871
#include <iostream>
using namespace std;

//int dp[2][12881];
int dp[12881];
int w[3403];
int v[3403];

int main()
{
    int i, j, n, c;
    cin >> n >> c;
    for (i = 1; i <= n; ++i)
        cin >> w[i] >> v[i];

    // 常规滚动数组实现
    //for (i = 1; i <= n; ++i)
    //    for (j = 1; j <= c; ++j)
    //        if (j >= w[i])
    //            dp[i%2][j] = max(dp[(i-1)%2][j], dp[(i-1)%2][j-w[i]]+v[i]);
    //        else
    //            dp[i%2][j] = dp[(i-1)%2][j];

    //cout << dp[n%2][c] << endl;

    // 对dp[i][]产生影响的只有dp[i-1][], 所以数组可以去掉一维
    for (i = 1; i <= n; ++i)
        for (j = c; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

    cout << dp[c] << endl;

    return 0;
}


完全背包

完全背包与 0-1 背包的区别仅在于一个物品可以选取无限次,而非仅能选取一次。

由于, f[i][j-w[i]]已由f[i][j-2*w[i]]更新过,对于第i件物品,重复选取,实现如下:
   for (j = w[i]; j <= t; ++j) // j 按从小到大顺序枚举,可实现重复选取
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

洛谷 1616
#include <iostream>
using namespace std;

long long dp[10000001];
int w[10001];
int v[10001];

int main()
{
    int i, j, n, t;
    cin >> t >> n;
    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> v[i];

    for (i = 1; i <= n; ++i)
        for (j = w[i]; j <= t; ++j) // j 按从小到大顺序枚举,可实现重复选取
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

    cout << dp[t] << endl;

    return 0;
}


多重背包问题
多重背包与 0-1 背包的区别仅在于一个物品可以选取m次。

单调队列求滑动窗口最值问题
/*https://www.luogu.com.cn/problem/P1886 */
#include <iostream>
#include <list>
#include <vector>
using namespace std;

int arr[100001];

int main()
{
    int i, n, k;
    cin >> n >> k;
    for (i = 0; i < n; ++i)
        cin >> arr[i];

    list<int> ls1; 
    list<int> ls2;
    vector<int> vec1;
    vector<int> vec2;

    for (i = 0; i < n; ++i)
    {
        // 单调递减队列求滑动窗口最大值
        while (ls1.size() > 0 && arr[ls1.back()] < arr[i])  //  新加入元素不满足单调递减
            ls1.pop_back();
        ls1.push_back(i);
        if (i-ls1.front()+1 > k)   // 队列中元素数量超过窗口大小
        {
            ls1.pop_front();
        }
        if (i+1 >= k)
            vec1.push_back(arr[ls1.front()]);

        // 单调递增队列求滑动窗口最小值
        while (ls2.size() > 0 && arr[ls2.back()] > arr[i])
            ls2.pop_back();
        ls2.push_back(i);
        if (i-ls2.front()+1 > k)
        {
            ls2.pop_front();
        }
        if (i+1 >= k)
            vec2.push_back(arr[ls2.front()]);
    }

    for (i = 0; i < vec2.size(); ++i)
        cout << vec2[i] << " ";
    cout << endl;
    for (i = 0; i < vec1.size(); ++i)
        cout << vec1[i] << " ";
    cout << endl;


    return 0;
}

/* https://www.luogu.com.cn/problem/P1776 */

/*  朴素思想

for (i = 0; i < n; ++i)          // 枚举物品种类
{
    cin >> v >> w >> m;
    for (j = W; j >= w; --j)     // 枚举背包容量
        for (k = 1; k <= m; ++k) // 枚举该种物品的数量
            dp[j] = max(dp[j], dp[j - k*w] + k*v);
}


为了获取dp[j], 需要使用dp[j-w], dp[j-2w], ... , dp[j-k*w]的状态。
当取k件该种物品,需要为这k件物品预留k*w的空间,剩下的j-k*w的空间就是之前存储的状态。由于第二层循环的j是递减的,当下一次容量为j-1时,整个遍历过程可理解为向左平移一格。
依此类推,当j递减到j-w时就和初始的状态重合了,
所以根据第i个物品的w,我们可以将整个dp数组划分成w个等价类,
分别以0,1,2,…,w-1为开始元素。
用单调递减队列对
     每个等价类f[i][j]=max(f[i−1][j],f[i−1][j−w]+v,f[i−1][j−2w]+2v,....+f[i−1][j−m*w]+m*v)求最大值,
时间复杂度就可以降至O(n*m)。
可看做求大小为m的滑动窗口最大值问题
*/

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

int main()
{
    int n, W , i, j, k;
    int v, w, m;   // value, weight, amount
    cin >> n >> W;
    vector<int> dp(W+1, 0);
    vector<int> prev;      // 滚动数组,记录上一组dp[]的值
    list<int> ls;          // 单调递减队列求滑动窗口最大值,滑动窗口的大小为m[i]

    for (i = 0; i < n; ++i)
    {
        prev = dp;
        cin >> v >> w >> m;
        for (j = 0; j < w; ++j)
        {
            ls.clear();
            for (k = j; k <= W; k += w)
            {
                /* 对于当前种类的物品,他的数量最多有m个,重量为w,
                 要用到的最早的状态是全取时k-s*w,所以要保证队首元素要在这个范围内。*/
                if (!ls.empty() && ls.front() < k - w*m)
                    ls.pop_front();

                /* k - ls[head]  背包剩余容量
                   (k - ls[head])/w 背包剩余容量能存几个重量为w的物品
                   (k - ls[head])/w*v 取这几个物品的价值 */
                if (!ls.empty())
                    dp[k] = max(dp[k], prev[ls.front()] + (k-ls.front())/w*v);

                /* 为了保持容量队列单调递减,背包容量k的dp值应小于队尾元素的dp值 */
                while (!ls.empty() && prev[ls.back()] + (k-ls.back())/w*v <= prev[k])
                    ls.pop_back();

                ls.push_back(k);
            }
        }
    }

    cout << dp[W] << endl;

    return 0;
}

/*
  任何一个非负整数,可以用一个以1为首项,2为公比的等比数列中的数来表示
  通过二进制优化,可将多重背包转换为0-1背包
*/

#include <iostream>
using namespace std;
const int MAXN = 10000;
int arrV[MAXN]; // value
int arrW[MAXN]; // weight
int dp[100001];

int main()
{
    int n, W , i, j, k, cnt = 0;
    int v, w, m;   // value, weight, amount
    cin >> n >> W;

    for (i = 0; i < n; ++i)
    {
        cin >> v >> w >> m;
        k = 1;
        do {
            m -= k;
            arrV[cnt] = v*k;
            arrW[cnt] = w*k;
            ++cnt;
            k = k << 1;
        } while (k <= m);

        if (m > 0)
        {
            arrV[cnt] = v*m;
            arrW[cnt] = w*m;
            ++cnt;
        }
    }

    for (i = 0; i < cnt; ++i)
        for (j = W; j >= arrW[i]; --j)
            dp[j] = max(dp[j], dp[j - arrW[i]] + arrV[i]);

    cout << dp[W] << endl;

    return 0;
}
 


http://www.ppmy.cn/news/26907.html

相关文章

【深度学习编译器系列】2. 深度学习编译器的通用设计架构

在【深度学习编译器系列】1. 为什么需要深度学习编译器&#xff1f;中我们了解到了为什么需要深度学习编译器&#xff0c;和什么是深度学习编译器&#xff0c;接下来我们把深度学习编译器这个小黑盒打开&#xff0c;看看里面有什么东西。 1. 深度学习编译器的通用设计架构 与…

05 基于STL的演讲比赛流程管理系统

文件基本上是黑马程序员的文档&#xff0c;部分添加自己需要的内容&#xff0c;仅用于自己学习&#xff01;链接&#xff1a;黑马程序视频课程GitHub:链接 演讲比赛流程管理系统 1、 演讲比赛程序需求 1.1 比赛规则 学校举行一场演讲比赛&#xff0c;共有12个人参加。比赛共…

制造企业为何要上数字化工厂系统?

以目前形势来看&#xff0c;数字化转型是制造企业生存的关键&#xff0c;而数字化工厂管理系统是一个综合性、系统性的工程&#xff0c;波及整个企业及其供应链生态系统。数字化工厂系统所要实现的互联互通系统集成、数据信息融合和产品全生命周期集成&#xff0c;将方方面面的…

Springboot扩展点系列之终结篇:Bean的生命周期

前言关于Springboot扩展点系列已经输出了13篇文章&#xff0c;分别梳理出了各个扩展点的功能特性、实现方式和工作原理&#xff0c;为什么要花这么多时间来梳理这些内容&#xff1f;根本原因就是这篇文章&#xff1a;Spring bean的生命周期。你了解Spring bean生命周期&#xf…

CMake构建静态库与动态库以及使用

CMake构建静态库与动态库一、任务二、准备工作三、编译共享库四、ADD_LIBRARY指令五、编译静态库5.1、SET_TARGET_PROPERTIES指令5.2、GET_TARGET_PROPERTY指令六、动态库版本号七、安装共享库和头文件八、使用外部共享库和头文件8.1、准备工作8.2、引入头文件搜索路径8.3、为 …

openCV—图像入门(python)

目录 目标 使用OpenCV 显示图像 写入图像 总结使用 使用Matplotlib 注:图片后续补充 目标 在这里,你将了解如何使用Python编程语言中的OpenCV库,实现读取、显示和保存图像的功能。具体来说,你将学习以下函数的用法:cv.imread() 用于读取图像,cv.imshow() 用于显示…

【1】linux命令每日分享——mkdir创建目录

大家好&#xff0c;这里是sdust-vrlab&#xff0c;Linux是一种免费使用和自由传播的类UNIX操作系统&#xff0c;Linux的基本思想有两点&#xff1a;一切都是文件&#xff1b;每个文件都有确定的用途&#xff1b;linux涉及到IT行业的方方面面&#xff0c;在我们日常的学习中&…

工信部印发《关于电信设备进网许可制度若干改革举措的通告》(附解读)

导 读 工业和信息化部近日印发《关于电信设备进网许可制度若干改革举措的通告》&#xff0c;内容包括调整部分电信设备监管方式、精简优化进网许可检测项目、公布进网许可审批承诺时限、延长进网试用批文有效期、实行电信设备产品系族管理等五项改革举措&#xff0c;自今年3月…