1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <fstream>
using namespace std;
const int MAX_LINE = 500;
const long MAX_TICKET = 100001;
int main()
{
//    fstream fin("/Users/yjgu/Code/C++_work/xcode/hihoCoder/t1038/input.txt");
    
    int n, value[MAX_LINE]={0};
    long m, need[MAX_LINE]={0}, income[MAX_TICKET]={0};
    cin >> n >> m;
    
    for (int i=0; i<n; i++)     // from 0 to n-1
        cin >> need[i] >> value[i];
    
    for (int i=0; i<n; i++)
    {
        for (long j=m; j>=need[i]; j--)         // 倒序可以避免一个样本被多次选中
            if (income[j-need[i]] + value[i] > income[j])
                income[j] = income[j-need[i]] + value[i];
    }
    cout << income[m] << endl;
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX