首页 > 其他分享 >动态规划01-背包问题

动态规划01-背包问题

时间：2024-08-25 20:25:52浏览次数：7  
标签：10 01 int cin 背包 物品 动态 dp

01背包问题

有 N N N件物品和一个容量是 V V V 的背包。每件物品只能使用一次。
第 i i i 件物品的体积是 V i V_i Vi​，价值是 W i W_i Wi​。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式：
第一行两个整数 N ， V N，V N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N N N行，每行两个整数 V i ， W i V_i，W_i Vi​，Wi​，用空格隔开，分别表示第 i i i 件物品的体积和价值。
输出格式：
输出一个整数，表示最大价值。
数据范围：
0 < N , V ≤ 1000 0<N,V≤1000 0<N,V≤1000
0 < V i , W i ≤ 1000 0<V_i,W_i≤1000 0<Vi​,Wi​≤1000
输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
8

解决思路

由于已经有很好的文章解答该问题，本文就不班门弄斧了，对于该问题的解决思路可以参照于hello algo 中的解答，本文主要给出代码实现以及注释
14.4 0-1 背包问题 - Hello 算法

代码实现

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
//使用数组v,n分别存储物品大小和价值
int v[N], w[N];
//使用dp[i][j]数组存储前i个物品中不超过容量j的最大价值
int dp[N][N];

int main()
{
    cin >> n >> m;
    //读入数据
    for(int i = 1; i <= n; i++)
        {
            cin >> v[i] >> w[i];
        }
    //使用两层循环进行状态转移
    //遍历每个物品i，对每个物品进行抉择
    for(int i = 1; i <= n; i++)
        {
            //遍历不同的背包容量，表示当前状态下的背包容量为j
            for(int j = 1; j <= m; j++)
                {
                    //当要选择的物品的体积不超过当前的背包容量，才可以选择放入
                    if(j >= v[i])
                    {
                        //从放入当前物品，背包容量减小，价值增加
                        //和不放入当前物品，背包容量不变的状态中选择一个价值大的
                        dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
                    }else
                    {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
        }
    cout << dp[n][m] << endl;
    return 0;
}

关于倒叙遍历问题可以看我的另一篇blog，里面有具体解释。
01背包问题空间优化中的内层循环问题

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        {
            cin >> v[i] >> w[i];
        }
    //由于在进行状态转移时，每次用到的都是上一次的数据
    //因此可以使用滚动数组的形式进行数据的存储，但是由于每次都来自于上方和左上方的数据
    //因此在进行从左向右遍历时第i - 1层的数据会被第 i 层的数据覆盖
    //需要使用倒序遍历的方式避免数据的覆盖
    for(int i = 1; i <= n; i++)
        {
            for(int j = m; j >= 1; j--)
                {
                    if(j >= v[i])
                    {
                        dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
                    }
                }
        }
    cout << dp[m] << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];

int main()
{
    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 = m; j >= v[i]; j--)
                {
                    //其实并没有什么优化，仅仅减少了一个判断条件
                    //由于我们不可以放入比当前背包容量还要大的物品
                    // 因此我们可以将这个if 判断放到for循环中进行处理
                    //使代码更加优雅
                    dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
                }
        }
    cout << dp[m] << endl;
    return 0;
}

完全背包问题

有 N N N件物品和一个容量是 V V V 的背包。每件物品可以使用无限次。
第 i i i 件物品的体积是 V i V_i Vi​，价值是 W i W_i Wi​。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式：
第一行两个整数 N ， V N，V N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N N N行，每行两个整数 V i ， W i V_i，W_i Vi​，Wi​，用空格隔开，分别表示第 i i i 件物品的体积和价值。
输出格式：
输出一个整数，表示最大价值。
数据范围：
0 < N , V ≤ 1000 0<N,V≤1000 0<N,V≤1000
0 < V i , W i ≤ 1000 0<V_i,W_i≤1000 0<Vi​,Wi​≤1000
输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
10

解决思路

对于该问题有两种思考方式，但是无论是哪一个最终的答案都是相同的

  • acwing上的思路

三重循环
将dp[i][j]分为k个集合，分别为选择第i个物品的数量从0到k,k为可以放入当前背包的最大个数，因此需要三重循环进行遍历
image.png
二重循环
简单的等式转换
通过上面两个式子，我们不难看出dp[i][j]中从dp[i-1][j-v]+w开始的一系列式子均可以通过将dp[i][j-v]加上w得到，从而将dp[i][j]的状态转移方程与k脱离关系，使得循环转换为二重循环
image.png
一维数组
类比于之前的01背包问题的优化，可以将其优化为一维数组

  • hello algo上的思路

相比于acwing上的层层推进，hello算法上的思路更加的一步到位。从真实的选取中理解该变化，我们将情况分为2个集合，对于第i个物品分别为不选取和选取，对于不选情况自然是背包容量不会减少同时对于第i个物品的选择已经结束，需要处理前i-1的物品的选择，也就是dp[i][j] = dp[i-1][j]，而对于选择的情况，由于物品的数量是无尽的，因此仍可以从i个物品中选择,dp[i][j] = dp[i][j-v]+w。
image.png
通过对比不难看到上述两种问题的状态转移方程仅有一处不同
在此同时给出上述两种方案的原地址
acwing算法基础课-动态规划
14.5 完全背包问题 - Hello 算法

代码实现

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];

int main()
{
    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 = 1; j <= m; j++)
        {
            for(int k = 0; k * v[i] <= j; k++)
            {
                dp[i][j] = max(dp[i][j],dp[i-1][j - k*v[i]] + k*w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}


#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];

int main()
{
    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 = 1; j <= m; j++)
        {
            //不放入的情况
            dp[i][j] = dp[i - 1][j];
            //放入的情况
            if(j >= v[i])
            {
                //由于每个物品的选择次数都成为了无数次
                // 因此做完第i个物品的决策之后依旧可以选择该物品
                dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}


#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];

int main()
{
    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++)
        {
            //如果不采用正序遍历，得到的结果反而会是上一层的数据，而不是本层的数据
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[m] << endl;
    return 0;
}

多重背包问题

有 N N N种物品和一个容量是 V V V 的背包。
第 i i i 种物品最多有 S i S_i Si​ 件，每件体积是 V i V_i Vi​，价值是 W i W_i Wi​。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数， N N N， V V V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N N N 行，每行三个整数 V i V_i Vi​, W i W_i Wi​, S i S_i Si​，用空格隔开，分别表示第 i i i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0 < N ≤ 1000 0<N≤1000 0<N≤1000
0 < V ≤ 2000 0<V≤2000 0<V≤2000
0 < V i , W i , S i ≤ 2000 0<V_i,W_i,S_i≤2000 0<Vi​,Wi​,Si​≤2000
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10

解决思路

对于该问题我们有多种解决方法

  • 三种循环遍历

按照之前的完全背包问题，使用一样的解决方法，仅仅增加一个约束条件，保证当前的 k k k在给出的 s s s的范围之内。

  • 利用二进制优化

由于上面的解决方法使用了三重循环，因此我们可以处理的数据大小仅仅在 1 0 2 10^2 102之内，对于 1 0 3 10^3 103的数据量会导致 TLE。
对于该问题我们采用将其转换为 0 0 0 1 1 1背包问题进行解决，但是如果像上面直接铺开，将一个数量为 10 10 10的背包分为 [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] [1,1,1,1,1,1,1,1,1,1] [1,1,1,1,1,1,1,1,1,1]的 0 0 0 1 1 1背包，并不会对该问题有任何优化。因此我们可以采用二进制的方式进行压缩也就是将一个数量为 10 10 10的背包分为 [ 1 , 2 , 4 , 3 ] [1,2,4,3] [1,2,4,3]，关于为什么不是 [ 1 , 2 , 4 , 8 ] [1,2,4,8] [1,2,4,8]是由于如果这样最终 4 − 8 4-8 4−8之间的数就无法表示，并且会超出 10 10 10的范围。

  • 使用单调队列优化

暂未实现

代码实现

#include <iostream>
using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int dp[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 0; k <= s[i] && k*v[i] <= j; k++)
            {
                dp[i][j] = max(dp[i][j],dp[i-1][j - k*v[i]] + k*w[i]);
            }
        }
    }
    cout << dp[n][m] << endl; 
    return 0;
}

#include <iostream>
using namespace std;

//需要开一个N*logS的数组大小
const int N = 2010, M = 25000;
int n, m;
int v[M], w[M];
int dp[N];

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        //将每一组的s数量按照从1,2,4,8的方式分为不同的01背包问题
        //如果一件物品规定的使用次数为 10 次，我们将其扁平化为三件物品：1*重量&1*价值，2*重量&2*价值，4*重量&4*价值，3*重量&3*价值
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        //按照每次乘2的规律进行分配
        while(k <= s)
        {
            cnt++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        //将剩余的s单独分为一个01背包
        if(s > 0)
        {
            cnt++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    //01背包问题模板
    n = cnt;
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= v[i]; j--)
        {
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl; 
    return 0;
}

分组背包问题

有 N N N组物品和一个容量是 V V V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 V i j Vij Vij，价值是 W i j Wij Wij，其中 i i i是组号, j j j是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N , V N,V N,V用空格隔开，分别表示物品组数和背包容量。
接下来有 N N N组数据：

  • 每组数据第一行有一个整数 S i S_i Si​，表示第 i i i个物品组的物品数量；
  • 每组数据接下来有 S i S_i Si​行，每行有两个整数 V i j , W i j Vij,Wij Vij,Wij用空格隔开，分别表示第 i i i个物品组的第 j j j个物品的体积和价值

输出格式
输出一个整数，表示最大价值。
数据范围
0 < N , V ≤ 100 0<N,V≤100 0<N,V≤100
0 < S i ≤ 100 0<S_i≤100 0<Si​≤100
0 < V i j , W i j ≤ 100 0<Vij,Wij≤100 0<Vij,Wij≤100

解决思路

对于分组背包问题我们可以采用将集合分组讨论的方法，对于一个 d p [ i ] [ j ] dp[i][j] dp[i][j]的集合，我们可以将其分为 N N N组，其中选择每组中第 k k k个数，因此其状态转移方程可以写为 d p [ i ] [ j ] = d p [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] dp[i][j] = dp[i - 1][j - v[i][k]] + w[i][k] dp[i][j]=dp[i−1][j−v[i][k]]+w[i][k]
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8

代码实现

#include <iostream>
using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N];
int dp[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 1; j--)
        {
            for(int k = 0; k < s[i]; k++)
            {
                if(j >= v[i][k])
                {
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

标签：10,01,int,cin,背包,物品,动态,dp
From： https://blog.csdn.net/yzd111/article/details/141503947

相关文章

  • 计算机考研真题知识点——2014（A）
    目录一、选择题二、填空题三、判断题四、名词解释五、综合题六、编程题一、选择题1、计算机算法是指问题求解步骤的描述。计算机算法是指解决问题的有限运算序列,它必须具备输入、输出和可行性、确定性和有穷性等5个特性。2、线性结构是一个有序数据元素的集合。（......
  • 反汇编动态调试器之x64dbg
    转载:https://cloud.tencent.com/developer/article/2337843 x64dbg是一款开源、免费、功能强大的动态反汇编调试器，它能够在Windows平台上进行应用程序的反汇编、调试和分析工作。与传统的调试器如Ollydbg相比，x64dbg调试器的出现填补了Ollydbg等传统调试器的不足，为反汇编调试......
  • 信息学奥赛初赛天天练-75-NOIP2016普及组-完善程序-二分答案、二分查找、贪心算法、贪
    1完善程序(单选题，每小题3分，共30分)郊游活动有n名同学参加学校组织的郊游活动，已知学校给这n名同学的郊游总经费为A元，与此同时第i位同学自己携带了Mi元。为了方便郊游，活动地点提供B(≥n)辆自行车供人租用，租用第j辆自行车的价格为Cj元，每位同学可以使用自己携带的钱或......
  • 算法笔记|Day34动态规划VII
    算法笔记|Day34动态规划VII☆☆☆☆☆leetcode198.打家劫舍题目分析代码☆☆☆☆☆leetcode213.打家劫舍II题目分析代码☆☆☆☆☆leetcode337.打家劫舍III题目分析代码☆☆☆☆☆leetcode198.打家劫舍题目链接：leetcode198.打家劫舍题目分析1.dp数组含义：d......
  • dp（2019csp-j纪念品）
    #include<bits/stdc++.h>usingnamespacestd;intn,T,a[101][101],v[101],f[10010];voidsolve(intd1,intd2){memset(f,0,sizeof(int)*(v[d1]+1));for(inti=1;i<=n;i++){intc=a[d1][i],w=a[d2][i];......
  • 微信不能打开，点击微信后显示无法定位程序输入点CreateTOolhelp32Snapshot于动态链接库
    问题描述：解决方法：修复动态链接库KERNEL32.dll重新安装动态链接库KERNEL32.dll检查应用程序兼容性与更新，或查找应用程序的补丁以修复可能存在的与kernel32.dll相关的兼容性问题下载最新版微信，卸载微信，重启电脑，退出杀毒软件后，重新安装最新版。原因：    1、系统文件损......
  • Vue3 + Vue Router实现动态路由导航
    Vue3+VueRouter实现动态路由导航随着单页面应用程序(SPA)的日益流行，前端开发逐渐向复杂且交互性强的方向发展。在这个过程中，Vue.js及其生态圈的工具（如VueRouter）为我们提供了强大的支持。本文将介绍如何在Vue3中使用VueRouter实现动态路由导航，帮助你增强应用的灵活......
  • [COCI2017-2018#5] Planinarenje
    这道题目是二分图博弈的板子介绍一下二分图博弈：设两部的节点分别为\(x_1,x_2,...,x_n\)和\(y_1,y_2,...,y_m\)，先手选择了\(x_i\)这个节点，则先手必胜当且仅当\(x_i\)是最大匹配的必须点（也就是说少了\(x_i\)的话最大匹配数会减少）证明：任选一个最大匹配，则\(x_i\)为匹配点，先手的策......
  • python-小理和01串（赛氪OJ）
    [题目描述]小理有一个 01 串，串中只包含 0 和 1 ，小理要把这个串划分成连续的 m 段，使得每一段至少包含一个 0 和一个 1 。小理想最大化 m ，m 最大是多少呢？输入格式：输入包含一行一个 01 串 S 。保证中至少包含一个 0 和一个 1 。输出格式：输出一行一个整......
  • 洛谷 P8615 [蓝桥杯 2014 国 C] 拼接平方数
    题面题目描述小明发现很有趣，首先，它是个平方数。它可以拆分为和，拆分出来的部分也是平方数。也有这个性质，我们权且称它们为：拼接平方数。可拆分，这有点勉强，我们规定，等都不算平方数。小明想：还有哪些数字是这样的呢？你的任务出现了：找到某个区间的所有拼接平方数。输入......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99