题目描述

获取最大价值的药草综合；

思路：

1）01背包问题，在有限的时间内，获取最大价值的药草
2）01背包问题模板：
    for i = 1...N
        for v = V...0
            f[v] = max(f[v],f[v-c[i]]+w[i]);
3)答案自然为f[V]

算法1

(暴力枚举) O(n^2)

C++ 代码

#include <iostream>

using namespace std;

int T,m;//总时间,药草总数目;
int f[1010];//存放最大价值的数组

int main(){
    int t,w;//采药时间,价值
    cin>>T>>m;
    for(int i=0 ;i<m;i++){
        cin>>t>>w;
        for(int j=T;j>=t;j--){
            f[j] =max(f[j],f[j-t]+w);
        }
    }
    cout<<f[T]<<endl;
    return 0;
}