题目链接:P1060 开心的金明
基本思路:
基本上和01背包原题一样,不同点在于这里要的是最大重要度*价格总和,我们之前原题是
f[j]=max(f[j],f[j-v[i]]+p[i]);
那么这里直接改成f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);就好了
其中f[j]代表的意义是当给定初始金币为j时重要度*价格的最大总和,也就是价值那里在这题变成了重要度*价格
再比较一下看看?
原题:f[j]=max(f[j],f[j-v[i]]+p[i]);
这题:f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
PS:我写了一篇很详细的01背包说明,如果下面ac代码有看不懂的地方可以去看看
对01背包的分析与理解(图文)
哎呀,第一次写的时没认真看题,数组开太小了,全部RE...
下面上ac代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[+];
ll v[+];//v单个价格
ll p[+];//p单个重要度
int main()
{
ll n,m;
cin>>n>>m;//n总钱数,m物品数
for(ll i=;i<=m;i++)//输入基础数据
{
scanf("%lld",&v[i]);
scanf("%lld",&p[i]);
}
for(ll i=;i<=m;i++)//遍历每个物品
for(ll j=n;j>=v[i];j--)//让当前剩余钱从n到v[i]
{
f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
}
cout<<f[n]<<endl;
}