训练日记 ：

背包模型

01 : 时间复杂度 $O(nm)$ 空间复杂度 $O(m)$

从每个物品选或不选进行考虑，每个物品等价于有体积、价值信息，背包有体积的限制在这个限制下尽可能装物品使得价值和最大,状态定义 ： f[i , j] 表示前 $i$ 个物品容量 $j$ 情况下最多装得物品价值和最大,状态计算 ： 从最后一个物品选或不选考虑，第 $i$ 个物品不选那么状态转移 ： $f_{i,j} = f_{i-1,j}$ , 如果第 $i$ 个物品选那么状态转移 : $f_{i,j} = max(f_{i,j},f_{i-1,j-v_i}+w_i)$

#pragma GCC optimize(3) 
#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>


int main()
{
    std::ios::sync_with_stdio(false) ;
    std::cin.tie(nullptr) ; 

    int n , m ; 
    std::cin >> m >> n ; 

    std::vector<std::vector<int>> f ( n + 10 , std::vector<int>( m + 10 , 0 )) ;
    std::vector<int> v(n + 10 , 0) , w(n + 10  , 0) ;

    for(int i = 1 ; i <= n ; ++ i) std::cin >> 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] = std::max(f[i][j] , f[i - 1][j - v[i]] + w[i]) ;
        }

    std::cout << f[n][m] << '\n' ;


    return 0 ; 
}

优化 :

显然的是每次状态转移只于上一次有关因此可以优化一维 $f_i$ 表示容量为 $i$ 情况下最多装有物品价值和最大，状态计算时第二层循环倒着来即可

#pragma GCC optimize(3) 
#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>


int main()
{
    std::ios::sync_with_stdio(false) ;
    std::cin.tie(nullptr) ; 

    int n , m ; 
    std::cin >> m >> n ; 

    std::vector<int> f ( m + 10 , 0 ) ;
    std::vector<int> v(n + 10 , 0) , w(n + 10  , 0) ;

    for(int i = 1 ; i <= n ; ++ i) std::cin >> v[i] >> w[i] ;

    for(int i = 1 ; i <= n ; ++ i)
        for(int j = m ; j >= v[i] ; -- j)
            f[j] = std::max(f[j] , f[j - v[i]] + w[i]) ;

    std::cout << f[m] << '\n' ;


    return 0 ; 
}