01背包问题

常见类型

这种问题主要内容大概是：
一个有n容量的背包，和一些有一定质量和价值的物品，要求在背包不超过装填范围的情况下带走价值最高的物品
聪明的同学已经开始说话了那么为什么不用贪心呢？因为贪心只能保证一个物品拿到最优解，不能保证全部是最优解。举个例子：
我有一个背包，有10的容量，一共有4件物品
w1 = 8, v1 = 9
w2 = 3, v2 = 3
w3 = 4, v3 = 4
w4 = 3, v4 = 3
如果用贪心算法，那么会默认放入“性价比”最高的w1，但是，放入w1后无法放入其他物品，但事实上我们发现如果装入w2,w3,w4，背包并没有溢出，而且总价值为10，明显大于只放入w1的情况。
所以我们需要用一种新的算法，让他可以考虑到所有的情况，那么我们就引入动态规划

本题代码

话不多说了，代码里啥都有：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t, m;
    // t表示背包的容量（在本题中是时间），m表示物品的数量（物品的数量和物品的种类数）
    cin >> t >> m;
    // w数组用来存储每个物品的重量（weight），v数组用来存储每个物品的价值（value）
    vector<int> w(m), v(m);
    // dp数组用来存储每种容量情况下背包的最大价值
    // dp[i]表示容量为i时的最大价值，初始化时所有值为0
    vector<int> dp(t + 1, 0);
    // 输入每个物品的重量和价值
    for (int i = 0; i < m; ++i){
        cin >> w[i] >> v[i];
    }
    // 外层循环遍历所有物品
    for(int i = 0; i < m; ++i){
        // 内层循环遍历每个可能的背包容量，从大到小更新dp数组
        // 从t开始，倒序遍历，确保每个物品只被考虑一次
        for(int j = t; j >= w[i]; --j){
            // dp[j]表示当前背包容量为j时的最大价值
            // 更新背包容量j时，考虑是否放入当前物品
            // 放入当前物品后，最大价值是dp[j - w[i]] + v[i]，表示在容量为j - w[i]时的最大价值加上当前物品的价值
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    // 输出最终背包容量为t时的最大价值，也就是我们要输出的答案 
    cout << dp[t];
    return 0;
}

怎么样是不是很简单
01背包就是这样的，同时也是最经典的动态规划问题
同时有野心的同学们可以看一下这个网站（CSDN的内容），学习一下其他的背包问题
ok就到这了