题目链接:

基本思路:

基本上和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代码有看不懂的地方可以去看看

哎呀,第一次写的时没认真看题,数组开太小了,全部RE...

 下面上ac代码

#include
     
      #define ll long longusing namespace std;ll f[30000+10];ll v[25+10];//v单个价格ll p[25+10];//p单个重要度int main(){    ll n,m;    cin>>n>>m;//n总钱数,m物品数    for(ll i=1;i<=m;i++)//输入基础数据    {        scanf("%lld",&v[i]);        scanf("%lld",&p[i]);    }    for(ll i=1;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<
      
       <