【洛谷p1060】开心的金明

(DP背包第一题,值得记录思路呀)

开心的金明【传送门】

洛谷算法标签:

【洛谷p1060】开心的金明

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

这道题显然是典型的01背包问题,首先我们显然可以由输入的第i个物体的价格v[i]和该物品的重要度p[i]算出该物体的【洛谷p1060】开心的金明也就是题目的要求(虽然不知道有什么用emmmm),接下来利用背包的典型套路:

for(int i=;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[],p[];//定义数组v表示物品价格,数组p表示重要度
int f[];
int c[];
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
cin>>v[i]>>p[i];
p[i]*=v[i];
}
for(int i=;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 ;
}

end-

上一篇:DedeCMS模板文件不存在,无法解析文档! 问题定位方法


下一篇:web_app框架