DP-01背包

01背包习惯上写成一维数组优化的形式：

1 for(int i=1;i<=n;i++)
2 {
3     for(int c=m;c>=0;c--)
4     {
5         if(c>=w[i])
6         f[c]=max(f[c],f[c-w[i]]+v[i]);
7     }
8 }

模板

//外层枚举每个物品，内层枚举空间

例题：

P1060 开心的金明：https://www.luogu.org/problem/P1060

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int f[50005], v[50], w[50];
 7 
 8 int main(){
 9     int n, m;
10     scanf("%d%d", &n, &m);
11     for(int i = 1; i <= m; i++){
12         scanf("%d%d", &v[i], &w[i]);
13         w[i] *= v[i];
14     }
15     for(int i = 1; i <= m; i++){
16         for(int j = n; j >= v[i]; j--){
17             if(j >= v[i]){
18                 f[j] = max(f[j], f[j-v[i]]+w[i]);
19             }
20         }
21     }
22     printf("%d
", f[n]);
23     return 0;
24 }

P1060

P1164 小A点菜：https://www.luogu.org/problem/P1164

取决于小A第i道菜是否要：

若钱充足，办法总数就等于吃这道菜的办法数与不吃这道菜的办法数之和；

若不充足，办法总数就只能承袭吃前i-1道菜的办法总数