noip 2005普及グループ採薬

タイトル
薬を採る
アルゴリズム#アルゴリズム#
(DP,バックパック問題)O(n m)O(nm)O(nm)古典01バックパック問題.
採薬総時間はリュックサック容量に相当し、1株当たりの薬は1つの物品に相当し、採薬時間はその物品の体積に相当し、薬草の価値は物品の価値に相当する.
時間の複雑さ
01リュックの問題の時間の複雑さは品物の数に等しい× バックパック容量であるため,本題の時間的複雑さはO(n m)O(nm)O(nm)である.
C++コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N]; // 01       

int main()
{
    cin >> m >> n; //            

    for (int i = 0; i < n; i++)
    {
        int v, w;
        cin >> v >> w; //           
        for (int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}