【动态规划】采药

贵有恒，何必三更起五更眠；最无益，莫过一日曝十日寒。

【动态规划】采药

时间限制: 1 Sec  内存限制: 64 MB

题目描述

山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值，在一段时间内如何让采到的草药价值最大。

输入

第一行有两个用空格隔开的整数T和M（1≤T，M≤100），T代表总共采药时间，M代表草药数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某种草药的时间和这株草药的价值。

输出

只包含一个整数，表示在规定的时间内可以采到的草药的最大总价值。

样例输入

70 3
71 100
69 1
1 2

样例输出

3

开的空间不能按照题目给的1-100，要开更大的空间。。。坑坑坑

#include <iostream>
#include <cstring>

using namespace std;

int t,m,f[1111],v[1111],w[1111];
void OneZeroPack(int m,int v,int w)  //0-1背包
{
    for(int i=m;i>=v;i--)
        f[i]=max(f[i],f[i-v]+w);
}

int main()
{
    while(cin>>t>>m)
    {
        for(int i=0;i<m;i++)
            cin>>v[i]>>w[i];
        memset(f,0,sizeof(f));
        for(int i=0;i<m;i++)
            OneZeroPack(t,v[i],w[i]);
        cout<<f[t]<<endl;
    }
    return 0;
}