初谈背包问题——01背包

背包问题第一讲——01背包问题

背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最大化某种价值或利益。问题的一般描述是：有一个背包，其容量为C；有一组物品，每个物品有重量w和价值v。目标是选择一些物品放入背包，使得它们的总重量不超过背包容量，同时总价值最大。

这个问题有两个主要变体：0/1背包问题和分数背包问题。

0/1 背包问题：

01背包问题是背包问题的的第一讲，也是动态规划问题的经典问题。在学习背包问题时首要学习的时01背包问题，其剩余的八讲背包都是在01背包的变体，从它这里延伸出来的，所以在学习背包问题时，01背包问题是基础之基础，务必要学会01背包问题。下面我们将对其进行介绍。

在01而背包这个问题中，我们想到的是01，为什么叫01，因为这个物品只有一个（特殊性），它所面临的选与不选，在选择这个物品时每个物品要么被选中就是'1'，要么被忽略，不去选择它就是'0'，不能部分选择。比如：我一个背包能装5kg，宝石2kg、价值2w，石头1kg、价值0w，翡翠6kg、100w，玛瑙3kg、5w，以上物品均只有一个。那么我的选择肯定是一块宝石一块玛瑙，这样背包恰好达到最终，价值也最大。这是一个离散问题，可以通过动态规划等方法求解。

分数背包问题：

在这个问题中，物品可以被部分选择，也就是可以选择物品的一部分。根据上面的例子，那么我们的理解就是可以切割，切割保证质量价值比，那么我们会选择切割6kg的翡翠，把它切割为5kg，这样得到的价值最大。这是一个连续问题，可以通过贪心算法等方法求解。

解决这些问题的方法包括动态规划、贪心算法、回溯法等。

接下来我将会给大家讲解背包九讲问题，分别为：01背包、多重背包、完全背包、混合背包、二位费用背包、分组背包、有依赖的背包、树形背包进行一一介绍，最后写一篇背包dp求方案数和具体方案的问题，并且介绍它们的优化解法，由于文章长度限制，编者将会分多篇文章进行编写。

01背包问题问题描述

一般的题目描述为有一个背包，其容量为C；有一组物品，每个物品有重量w和价值v。目标是选择一些物品放入背包，使得它们的总重量不超过背包容量，同时总价值最大，求出价值最大化。

一般解法：

下面代码为01背包问题的一般解法，采用的是二位数组f[i][j]来递归求解，注释在代码上，这个一般解法又可以成为暴力解法，主要就是遍历一遍物品数，遍历一遍背包容量，状态转移方程为f[i][j]=f[i-1][j]（w[i]>j时），f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])（w[i]<=j时）,当去选择是自然就面临着用背包容量去换价值，自然贪心的思想就是想要最小的背包容量去换取最大的价值，每一步选择的最优，必然导致结果的最优，也就是说局部的最优导致全局最优，这就是动态规划（DP）的思想。

#include<stdio.h>
int f[100][100];//f[i][j]为在前i件物品中背包容量为j所选择最大化
int w[100],v[100];//w:物品重量，v:物品价值
int max(int x,int y){
  return x>y?x:y;
}
int main(){
  int i,j,n,m;//n为最大物品数，m为最大背包容量
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d%d",&w[i],&v[i]);
  }
  for(i=1;i<=n;i++){//i物品数，把所有物品遍历一遍，要么选要么不选
    for(j=1;j<=m;j++){//j背包容量
      if(w[i]>j){//第i个物品的重量大于此时背包容量j
        f[i][j]=f[i-1][j];//那就不选i
      }else{//如果小于背包容量就选
        f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
          //在前i-1个物品基础上，面对第i个物品，你选了，那就要付出w[i]的代价，来换取价值为v[i]
          //如果你没选i号物品，那么你还有j背包容量供你选择i号物品前面的物品
          //如果你选了i号物品，那么你的背包容量将减少w[i]，剩余j-w[i]供你选择i号物品前面的物品
          //因为是最优解问题，要寻找最大值，到底是选了i号物品价值更大还是不选i号物品价值更大
          //这里并不是选了就大，比如第i个物品是个石头，i-1是个钻石，你选了石头，钻石就放不开了，此时不选i号物品最优
      }
    }
  }
  printf("%d",f[n][m]);
}

优化解法：

那么还有没有优化解法呢，答案是肯定有的，那就是空间上把f[i][j]优化成一维数组dp[i]，也叫滚动数组，每滚动一次，dp[j]就会更新一遍，dp[i]只记录一行的数据，让j值逆序循环，更新dp[j]的值，因为j是逆序循环，dp[j]的值会优先于dp[j-v[i]]更新，也就是说用旧值dp[j-v[i]]去更新dp[j]，相当于用上一行的dp[j-v[i]]更新dp[j]，这里比较抽象，可以自己动手写一写理解一下，具体代码如下：

#include<iostream>
using namespace std;
int dp[205],w[35],v[35];
//dp[i]表示将物品放入背包容量为i的背包中最大价值
int n,m;
int main(){
  cin>>m>>n;
  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--){//这边把背包容量控制在大于v[i]，防止再出现if判断背包容量与重量的关系
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
  }
  cout<<dp[m]<<endl;
  return 0;
}

具体视频讲解B站董晓老师讲的很好可以看一下：E08【模板】背包DP 01背包_哔哩哔哩_bilibili

对于01背包问题，编者把自己的想法分享给大家，望对大家有帮助，由于本人水平有限，一些地方可能说不清楚或者错误的地方，望各位大佬指出共同进步，执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。下一篇更新多重背包问题。