算法
分组背包

f[i][j]表示的是前i组物品，总体积不大于j的集合（所有选法）（最大值）。

①不选第i组物品；②选第i组的某个物品。

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
#include<iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            f[i][j] = f[i - 1][j]; //这个式子一定是写在选择分组背包的外面。 
            for(int k = 1; k <= s[i]; k ++) {
            if(j >= v[i][k])    
                f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    cout << f[n][m] << endl;
    return 0;
}
最长上升子序列

f[i]表示的是以第i个数结尾的最长上升子序列

因为可能不是以第i-1个数结尾的时候上升子序列最大，所以求解时是求个max。

最后也是因为不一定是以最后一个数结尾的时候，上升子序列最大。

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
#include<iostream>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for(int i = 1; i <= n; i ++) {
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
        
    int res = 0;
    for(int i = 1; i <= n; i ++)    res = max(res, f[i]);
    
    cout << res << endl;
    return 0;
}