训练日记

背包模型

状态定义 : $f_i$ 表示 装一些物品使得剩余容量为 i 该方案可行，状态计算 ：$f_{i - v_i} |= f_{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 m , n ;
    std::cin >> m >> n ;

    std::vector<int> f (m + 10 , 0) , v (n + 10 , 0) ;
    f[m] = 1 ; 
    for(int i = 1 ; i <= n ; ++ i) std::cin >> v[i] ; 

    for(int i = 1 ; i <= n ; ++ i)
        for(int j = v[i] ; j <= m ; ++j)
            f[j - v[i]] |= f[j] ;

    for(int i = 0 ; i <= m ; ++ i) if ( f[i] ) return std::cout << i << '\n' , 0 ;         

    return 0 ; 
}