(DP背包第一题,值得记录思路呀)
洛谷算法标签:
01背包问题的思路分析见【总结】01背包问题
这道题显然是典型的01背包问题,首先我们显然可以由输入的第i个物体的价格v[i]和该物品的重要度p[i]算出该物体的也就是题目的要求(虽然不知道有什么用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-