【洛谷p1060】开心的金明

（DP背包第一题，值得记录思路呀）

开心的金明【传送门】

洛谷算法标签：

01背包问题的思路分析见【总结】01背包问题

这道题显然是典型的01背包问题，首先我们显然可以由输入的第i个物体的价格v[i]和该物品的重要度p[i]算出该物体的也就是题目的要求（虽然不知道有什么用emmmm），接下来利用背包的典型套路：

for(int i=1;i<=m;i++)
        for(int j=n;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+p[i]);//这里运用了一维数组来减少空间；

逐步求出f[n]，得到最后的结果。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>//一坨莫名长的头文件
using namespace std;
int n,m;
int v[26],p[26];//定义数组v表示物品价格，数组p表示重要度
int f[50000];
int c[26];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i]>>p[i];
        p[i]*=v[i];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+p[i]);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

end-