01背包裸题

体重的草药的价值就是背包的价值，采草药的时间就是背包的总容量，每个草药的时间就是每个背包的体积。

$ 时间复杂度O(NM),空间复杂度O(M)$

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 1e3 + 10;

int n, m;
int t[N], w[N], f[N];

int main(){
    cin >> m >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> t[i] >> w[i];

    for (int i = 1 ; i <= n ; i ++){
        for (int j = m ; j >= t[i] ; j --){
            f[j] = max(f[j], f[j - t[i]] + w[i]);
        }
    }

    cout << f[m];
    return 0;
}