常见背包问题

一.前言

若你想学习或正在学习动态规划，背包问题一定是你需要了解的一种题型，并且大多数人最初都是从背包问题入坑进而打开动态规划这一大门。背包问题分为多种，你可以先掌握最常见的主要是三类：01背包、完全背包、多重背包

二.分析背包问题

1)01背包

在考虑一个物品时(从目标容器到物品大小容器考虑(保证只放一次))，放入当前物品后，所剩空间只能考虑其他物品

★状态:考虑了前i个物品，大小为j的容器能放入的最大价值的商品

转移方程:f[i][j]=max(f[i-1][j],f[i-1][j-V[i]])+W[i])

转移方程:dp[j]=max(dp[j-V[i]],dp[j]])(注:等号右边的dp为上个循环的结果，即考虑当前物品前面的所有物品的结果)

2)多重背包

在考虑一个物品时，将放不同个数看成不同物品，即可转化为01背包问题

3)完全背包

在考虑一个物品时(从物品大小容器到目标容器考虑(保证应放尽放))，放入当前物品后所剩空间只能考虑其他物品

三.例题

1)题目

01背包
有 n 件物品和一个容量是 v 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v i，价值是 w i。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程，上面有详细解释
int main(){
    int n,m;
    scanf("%d%d",&n,&m); //输入物品数量和背包容量
    for(int i = 1;i <= n;i ++) scanf("%d%d",&v[i],&w[i]); //输入每个物体的体积和价值
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;j ++){
            f[i][j] = f[i - 1][j]; //合并内容
            if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //已经把f[i][j]赋值为f[i - 1][j]了，现在就可以直接用f[i][j]了
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

2)题目

有 n种物品和一个容量是v的背包，每种物品都有无限件可用。
第 i 种物品的体积是 v i，价值是 w i。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

代码

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N][N];

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

3)题目

有 n 种物品和一个容量是 v 的背包。
第 i 种物品最多有 s i 件，每件体积是 v i，价值是 w i。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int v[N], w[N], s[N];
int f[N][N];
int n, m;

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 ++){
                if(j >=  k * v[i]){
                    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}