背包问题大合集--算法模板

01背包

一维数组优化状态转移方程

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], n, V, w, v;
int main(){
  cin >> n >> V;//物品数量和背包容量
  while(n -- ){
    cin >> w >> v;//物体体积和价值
    for(int i = V; i >= w; -- i) {//注意只能倒序遍历
      a[i] = max(a[i], a[i - w] + v);
    }
  }
  cout << a[V] << '\n';
  return 0;
}

完全背包

一维数组优化状态转移方程

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], n, V, w, v;
int main(){
  cin >> n >> V;//物品数量和背包容量
  while(n -- ){
    cin >> w >> v;//物体体积和价值
    for(int i = w; i <= V; ++ i) {//注意只能顺序遍历
      a[i] = max(a[i], a[i - w] + v);
    }
  }
  cout << a[V] << '\n';
  return 0;
}

多重背包

01背包加强版

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int dp[N], n, m, w, v, s;

int main() {
  cin >> n >> m;//商品数量和背包容量
  for(int i = 1; i <= n; ++ i) {
    cin >> w >> v >> s;//体积、价值、数量
    while(s --) 
      for(int j = m; j >= w; -- j) 
        dp[j] = max(dp[j], dp[j - w] + v);
  }
  cout << dp[m] << '\n';
  return 0;
}

二进制优化版

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 6;
int dp[N], n, m, w, v, s;

int main() {
  cin >> n >> m;//商品数量和背包容量
  for(int i = 1; i <= n; ++ i) {
    cin >> w >> v >> s;//体积、价值、数量
    for(int k = 1; k <= s; s -= k, k *= 2) {//二进制优化
      for(int j = m; j >= k * w; -- j) dp[j] = max(dp[j], dp[j - k * w] + k * v);
    }
    for(int l = m; l >= s * w; -- l) dp[l] = max(dp[l], dp[l - s * w] + s * v);
  }
  cout << dp[m] << '\n';
  return 0;
}

二维费用背包

很简单啊，就是在一维的基础上加一重循环。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], n, V, M, v, m, w;

int main() {
  cin >> n >> V >> M;//商品数量、背包体积、背包重量
  while(-- n) {
    cin >> v >> m >> w;//商品的体积、重量、价值
    for(int i = V; i >= v; -- i)
      for(int j = M; j >= m; -- j)
        a[i][j] = max(a[i][j], a[i - v][j - m] + w);
  }
  cout << a[V][M] << '\n';
  return 0;
}

分组背包

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int dp[N][N], n, m, w, v, s;
int main() {
  cin >> n >> m;//商品组数和背包容量
  for(int i = 1; i <= n; ++ i) {
    cin >> s;//每组商品个数
    while(s --) {
      cin >> w >> v;//商品的体积、价值
      for(int j = m; j >= 0; -- j) {
        dp[i][j] = max(dp[i - 1][j], dp[i][j]);//选与不选
        if(j >= w) dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
        }
    }
  }
  cout << dp[n][m] << '\n';
  return 0;
}

总结

就以上这些背包问题啊。注意以上的背包问题，完全背包需要顺序遍历，其他的背包都是逆序遍历，因为都是一维背包演变过来的。以上的代码模板均是正确的，放心使用。