#dp背包#北京大学机试题

https://www.acwing.com/problem/content/3448/

想法：套二维数组dp公式，先找到小问题及转移方程

解法：将题目所述数据读入整型变量c，n和价格数组p[]以及评价数组v[]；

1.新建一个大小为1001*102的dp数组dp[i][j]，每个元素表示：在预算为j元的时候，考虑从0到j号菜品组合中评价最高的评分

2.双for循环遍历，注意i是从1到c，j是从1到n（上限取等号）

3.对于某个i，遍历的每一个j：

a.检查j菜品是否超出价格i，若超出则将上一个菜品对应的评分（dp[i][j-1]）赋值给当前评分（dp[i][j]）

b.若没有超出，则选择上一个菜品对应的评分（dp[i][j-1]）和预算减去该菜品价格时对应的评分加上该菜品的v值中的较大值（max(dp[i][j-1],dp[i-p[j-1]][j-1]+v[j-1])）注意菜品下标都为j-1

c.循环结束，打印dp[c][n]即可

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int c,n;
    scanf("%d%d",&c,&n);
    int p[n+1],v[n+1];
    for(int i=0;i<n;i++){
        scanf("%d%d",&p[i],&v[i]);//p[i]记录价格，v[i]记录评价
    }
    int dp[1001][102];//dp[c][v]二维矩阵，记录c价格下从0到v号商品最大的评价分数
    for(int i=0;i<=c;i++) dp[i][0]=0;
    for(int j=0;j<=n;j++) dp[0][j]=0;
    for(int i=1;i<=c;i++){
        for(int j=1;j<=n;j++){
            if(i-p[j-1]<0){
                dp[i][j]=dp[i][j-1];
            }
            else{
                dp[i][j]= max(dp[i][j-1],dp[i-p[j-1]][j-1]+v[j-1]);
            }
        }
    }
    printf("%d",dp[c][n]);
    return 0;
}