代码编织梦想

01背包问题

0-1背包问题是一个经典问题,特别是在算法和动态规划领域。问题是关于一个小偷,他有一个可以携带最大重量的背包,并且他有一组物品,其中每个物品都有自己的价值和重量。小偷希望在不超过背包所能承载的最大重量的情况下,最大化他从这些物品中获得的总价值。问题是他只能拿走一件物品一次,或者根本不能拿走 - 因此得名 0-1。

题目:

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大
输出最大价值。

输入格式

第一行两个整数,N,V用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤10000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8

思路:

  1. 创建一个二维数组,其中行代表物品,列代表背包的总重量,从 0 到最大重量。
  2. 将第一行第一列初始化为0,因为如果没有物品或者最大权重为0,则最大值为0。
  3. 对于每个项目,迭代每个总重量。如果物品的重量小于或等于当前总重量,则取当前物品的重量加上之前物品的剩余重量值之间的最大值,以及不包括当前物品的最大值。
  4. 可以获得的最大值是二维数组右下角的值。

解题步骤(二维数组):

1 状态表示:int f[ i ][ j ];          表示前 i个物品,背包容量 j下的最大价值;

2 状态转移方程(根据最后一步的状况分条件讨论)

  f[i][j]   :不选i件物品   ------>f[i - 1][j]
             选第i件物品 ------->w[i] + f[ i-1 ][ j - v[i] ] + w[i](注:当前的背包容量是 j ,如果把背包全部清空都放不下 i ,那么只能将 i 舍弃,即为不选 i,需要j - v[i] >= 0,此时才可装下第 i 个物品)

f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);

代码:

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;

int n , m;//n表示所有物品的个数,m表示背包的容量
int v[N],w[N];//v表示物品的体积,w表示物品的价值
int f[N][N];//表示前 i个物品,背包容量 j下的最大价值;


int main ()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n;i++)  cin >> v[i] >> w[i];
    
    //f[0][0~m] 均为0;且其在全局定义,所以从1开始赋值;
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 1; j <= m;j ++)
        {
            if(v[i] <= j)//能放入第 i 件物品的情况下,求f[i][j]
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            else//不能放入第 i 件物品的情况下,求f[i][j]
                f[i][j] = f[i - 1][j];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

优化:一维数组(滚动数组)

注意:使用一维数值优化时遍历要逆序

原因:(f[ j ] 容量为 j 的背包所背的最大价值)

  一维数组的状态转移方程为 

​​​​​​​f[ j ] = max( f[ j ] , f[ j - v[ i ]] + w[i]]  

若为正序

当最外层循环到  i  =  i 层时 ,其上一层为  i  -  1;v[ i ] = 1 , m = 5。

j = 3时,我们需要判断 f [ 3 ] = max ( f [ 3 ], f [ 2 ] + w [ i ] ) ;
如果此时,我们将f [ 3 ] 更新了,那么在下一个 j 循环,j = 4 时,

我们要判断 f [ 4 ] = max ( f [ 4 ], f [ 3 ] + w [ i ] ) ;

那此时,我们使用的就是刚刚被更新的f [ 3 ],即 f [ i ] [ 2 ],而非上一层的 f [ i-1 ] [ 2 ],因为上一层的 f [ i-1 ] [ 2 ]已经被更新成当前层的f [ i ] [ 2 ]了.所以结果为错的。

若为逆序

当最外层 i 循环到 i 时, v[i] = 1 , m = 5,我们会将 j 循环

当j = 4时,我们需要判断 f [ 4 ] = max ( f [ 4 ], f [ 3 ] + w [ i ] ) ;

我们此时只会更新 f [ 4 ] 的值.

在下一次判断时,我们需要判断 f [ 3 ] = max ( f [ 3 ], f [ 2 ] + w [ i ] ) ;

最终。刚刚更新的值f [ 4 ]与下一次的判断f [ 3 ]无关,因此,只需要将 j 逆序遍历,就不会影响上一层的f [j  -  v[ i ]]。

代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;//n表示所有物品的个数,m表示背包的容量
int v[N], w[N];//v表示物品的体积,w表示物品的价值
int f[N];//表示物品的状态
int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)  cin >> v[i] >> w[i];//输入数据

    //f[j] 容量为 j 的背包所背的最大价值;
    
    for (int i = 1; i <= n; i++)//遍历物品
    {
        for (int j = m; j >= v[i]; j--)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Mr_AN_2023/article/details/136005251

01背包问题一维与二维解法-爱代码爱编程

算法思路 f[i][j]:表示的是只看前i个物品里面,体积为j种最大的价值 那就分为两种,拿和不拿 1.f[i][j]=f[i-1][j] 你不拿的情况和f[i-1][j]一致 2.f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])  从小到大依次计算即可   #include<iostream> #inc

01背包问题(二维-->一维)-爱代码爱编程

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 v,价值是 w 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。   输出最大价值。 输入格式 第一行两个整数, N,V ,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi, wi,用空格

背包问题总结【0-1背包、完全背包、排列组合问题】_uoyaij_的博客-爱代码爱编程

背包问题总结 背包问题0-1背包问题解法一:二维DP数组解法二:一维DP数组 完全背包问题组合和排列问题 背包问题 背包问题包括以下几种情况: 图片来自carl哥的:代码随想录 侵删 0

背包问题(01背包)动态规划二维dp+一维优化版-爱代码爱编程

背包问题(01背包)动态规划 本文包含动态规划解决背包问题的二维dp数组版本及优化后的一维dp数组版本,代码均用Java实现。 题目描述 有 N件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体

背包问题(01背包+完全背包)的一维+二维解法-爱代码爱编程

一、背包问题一维+二维解法 二、背包问题注意点: 1 . dp数组含义: (1)01背包:往容量为j的背包放入前i个物品,所能获得的最大价值(一个物品只能放入一次) (2)完全背包:往容量为j的背包放入前i个物

算法系列-爱代码爱编程

💕"趁着年轻,做一些比较cool的事情"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是算法系列--动态规划--背包问题(1)--01背包介绍

【力扣一轮】数组-爱代码爱编程

旋转矩阵 题目链接 随想录链接 旋转的方式把数字一个接一个写入矩阵中。 这时需要用到循环不变量,它是一个循环,每次处理的时候需要处理的方式是一样的,而不是有着条件的限制。 对于这道题,循环不变量就是边元素的处理,只

【算法】noip2003神经网络-爱代码爱编程

题目描述 人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向,兰兰同学在自

嵌入式学习第三十五天!(算法)-爱代码爱编程

算法:解决特定问题求解步骤 1. 算法的设计:     1. 正确性:语法正确;合法的输入能得到合理的结果;对非法的输入,给出满足要求的规格说明;对精心选择,甚至刁难的测试都能正常运行,结果正确;     2. 可读性:便于交流,阅读,理解(高内聚,低耦合);     3. 健壮性:输入非法数据,能进行相应的处理,而不是产生异常;     4.

c语言笔记14-爱代码爱编程

指针1         在C语言中给内存单元的编号起了个名字叫做指针,通俗来说就是地址。(内存单元编号=地址=指针) 1.指针变量与地址 int a=10;  int* p=&a;   *  说明了这里p的是指针变量;int*说明p是一个整形指针;int说明p指向的对象a是一个整形;&a是取出a的地址; 总的来说就是取出a的地址存

cow exhibition g的来龙去脉-爱代码爱编程

[USACO03FALL] Cow Exhibition G - 洛谷 曲折经过 爆搜 一开始没什么好的想法,就针对每头奶牛去or不去进行了爆搜。 #include <cstdio> #include <algorithm> using namespace std; #define maxn 405 int iq[maxn

【算法】二分算法——x的平方根-爱代码爱编程

本节博客使用“二分边界算法”对“x的平方根”这一题目进行求解,有需要借鉴即可。 目录 1.题目2.暴力求解3.二分算法求解4.取值范围细节5.总结 1.题目 题目链接:LINK 2.

c动态内存管理-爱代码爱编程

malloc calloc realloc free 原则:谁申请,谁释放,防止内存泄漏 #include<stdio.h> #include<stdlib.h> int mian() { i