背包问题

1. 0-1背包问题

0-1背包问题为：有N件物品和一个容量为V的背包，第i件物品的体积和价值分别为volume[i]和value[i]，求解将哪些物品装入背包可以获得最大价值
针对0-1背包问题，每个物品都有放或者不放两个选择，并且放只能放一次，问题的状态可以表述为：
f[i][j]:表示前i件物品放入容积为j的背包的最大价值，其状态转移方程就可表述为：
f[i][j] = max(f[i-1][j], f[i-1][j-volume[i]]+value[i])
代码实现如下：

int find_max_value(vector<vector<int>>& items, int n, int v){
  int f[1005][1005] = {0};
  for(int i = 1 ; i <= n ; i++){
    for(int j = 0 ; j <= v ; j++){
	  f[i][j] = f[i-1][j];
	  if(j>= items[i-1][0]){
	    f[i][j] = max(f[i][j],f[i-1][j-items[i-1][0]] + items[i-1][1]);
	  }
    }
  }
  return f[n][v];
}

考虑代码优化：从代码中我们可以看到，转移方程中，每个变量只与上一个变量有关系，因此我们没有必要进行全部存储，可以通过使用一维数组的方法，为了保证变量刷新的正确性，采用从后往前刷的方式，确保已更新的数据对未更新的数据不产生影响。
代码实现如下：

int find_max_value(vector<vector<int>>& items , int n , int v){
  int f[1005] = {0};
  for(int i = 0 ; i < n; i++){
    for(int j = v ; j - items[i][0] >=0 ; j--)
      f[j] = max(f[j],f[j-items[i][0]]+items[i][1]);
  }
  return f[v];
}

2. 完全背包问题

完全背包问题的描述类似于0-1背包问题，其唯一的不同为：完全背包问题中的物品可以重复选择。最简单的思路为分别测试每个物品装若干个，直到体积不够为止。
具体代码如下所示：

int find_max_value(vector<vector<int>>&items, int n , int v){
  int f[1005] = {0};
  for(int i = 0 ; i < items.size(); i++){
    for(int j = items[i][0]; j <= v; j++){
      for(int k = 1 ; j - k * items[i][0] >= 0 ; k++)
        f[j] = max(f[j],f[j-k*items[i][0]]+k*items[i][1]);
    }
  }
  return f[v];
}

代码优化：上述代码可以转为如下的优化代码：

int find_max_value(vector<vector<int>>&items, int n , int v){
  int f[1005] = {0};
  for(int i = 0 ; i < items.size(); i++){
    for(int j = items[i][0]; j <= v; j++){
        f[j] = max(f[j],f[j-items[i][0]]+items[i][1]);
    }
  }
  return f[v];
}

具体优化原理为，当体积不断上升的时候，需要的状态在之前已经计算过了
规律：从01背包和完全背包可以看出，代码的不同只有在二次循环中，01背包从大到小刷新，完全背包从小到大刷新

3. 多重背包问题

多重背包问题和0-1背包问题相比，每个物品有一个可挑选的上限，最简单的思路为对于每一个物品，重复放入挑选上限次，这样就转化为01背包问题，例如物品A的挑选上线为4，就在物品池中放入四个A。
具体代码如下所示：

int find_max_value(vector<vector<int>>&items, int n , int v){
  int f[1005] = {0};
  vector<pair<int,int>>vec;
  for(int i = 0 ; i < items.size(); i++){
    for(int j = 0 ; j < items[i][2]; j++){
      vec.push_back({items[i][0],items[i][1]});
    }
  } //通过此步操作转为01背包问题
  for(int i = 0 ; i < vec.size(); i++){
    for(int j = v; j >= vec[i].first ; j--){
      f[j] = max(f[j],f[j-vec[i].first]+vec[i].second);
    }
  }
  return f[v];
}

代码优化：分析上述代码中存在的问题，我们发现将一个数字分解为若干个1的方法的复杂度过高，于是我们想到使用二进制的方法进行优化，例如 数字7 可以拆分为 1 ， 2 ， 4 。通过这三个数字的组合我们可以得到1-7的所有数字，10 可以拆分为 1， 2 ， 4 ， 3。通过这四个数字的任意组合我们可以得到1-10的所有数字，于是在第一步代码拆分的地方可替换为下面的二进制拆分法。

for(int i = 0 ; i < items.size(); i++){
  for(int k = 1 ; k <= items[i][2]; k*=2){
    items[i][2] -= k;
      vec.push_back({k*items[i][0],k*items[i][1]});
  }
  if(items[i][2] > 0)
      vec.push_back({items[i][2]*items[i][0],items[i][2]*items[i][1]});
}

其他代码保持不变

4. 混合背包问题

混合背包问题其实就是前面的几种背包问题的混合，有的物品只能选用一次，有的物品可以选用无数次，有的物品只能选用有限次，针对不同类别的物品采用各自的更新方法即可。
具体代码如下所示：

struct myitem{
  int vol;
  int val;
  int num;
}
int find_max_value(vector<vector<int>>&items,int n,int v){
  int f[1010] = {0};
  vector<myitem>vec;
  for(int i = 0 ; i < items.size(); i++){
    if(items[i][2] == -1)
      vec.push_bakc({items[i][0],items[i][1],items[i][2]});
    if(items[i][2] == 0)
      vec.push_back({items[i][0],items[i][1],items[i][2]});
    if(items[i][2] > 0){
      for(int k = 1; k <= items[i][2]; k *= 2){
         items[i][2] -=k;
         vec.push_back({items[i][0]*k,items[i][1]*k,-1});
       }
      if(items[i][2] > 0)
        vec.push_back({items[i][0]*items[i][2],items[i][1]*items[i][2],-1});
     }
  }
  for(int i = 0 ; i < vec.size();i++){
    if(vec[i].num != 0)
      for(int j = v; j >= vec[i].vol; j--)
         f[j] = max(f[j],f[j-vec[i].vol]+vec[i].val);
    else
      for(int j = vec[i].vol; j<= v; j++)
        f[j] = max(f[j],f[j-vec[i].vol]+vec[i].val);
  }
  return f[v];
}

5. 二维费用的背包问题

二维费用的背包问题在一维费用的背包问题上增加了一个约束条件，比如对背包的承重进行限制等
具体代码如下所示：

int find_max_val(vector<vector<int>>&items,int n,int v,int w){
  int f[1010][1010] = {0};
  for(int i = 0 ; i < n ; i++){
    for(int j = w ; j >= items[i][0]; j--){
      for(int k = v; k >= items[i][1]; k--)
        f[j][k] = max(f[j][k],f[j-items[i][0]][k-items[i][1]]+items[i][2]);
    }
  }
  return f[w][v];
}

6. 分组背包问题

分组背包问题相较于01背包问题增加了一个约束条件是，组内元素只能挑选一个,因此很直觉的思路为分别测试组内每一个物品带来的价值
具体代码如下所示

int find_max_val(unordered_set<vector<vector<int>>>&items,int v){
  int f[110] = {0};
  for(auto & item : items){
    for(int j = v ; j >= 0 ; j--)
      for(int k = 0 ; k < item.size(); k++)
        if(j-item[k][0] >= 0)
          f[j] = max(f[j],f[j-item[k][0]]+item[k][1]);
  }
  return f[v];
}