一.题目链接:P1064 金明的预算方案
二.思路
1.一共只有五种情况
@1.不买
@2.只买主件
@3.买主件和附件1(如果不存在附件也要运算,只是这时附件的数据是0,也就是算了对标准的结果也没影响)
@4.买主件和附件2
@5.买主件和两个附件
2.因为要求的是重要度*价格,那么数组就直接存重要度*价格,最后输出f[n]就是答案
附件不一定刚好有两个,可是如果没有的话数组的值是空的,也就好像虚无缥缈的灵魂一样,用了也没关系
3.主件和附件要构建一层联系,一个个输入物品时肯定混杂着主件和附件,那么对于主件数组,如果编号为0就存,编号不为0就让他空着,对于附件数组,就用编号作为下标就好了,这样就在主件和附件中构建一层联系,可以随时通过主件找到所属附件
4.判断各种情况时要考虑能不能执行,也就是剩余金币够不够的问题
5.然后循环的时候用滚动数组优化空间,不懂的可以去了解一下
6.各种情况都比较一次,找出最好的就好了
7.本来存重要度的数组现在存重要度*价格,可以简化代码
三.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[+];
ll main_v[+];//v主件单个价格
ll main_vp[+];//主件单个重要度p*价格v
ll belong_v[+][];//附件价格v
ll belong_vp[+][];//附件重要度p*价格v
int main()
{
std::ios::sync_with_stdio(false);
ll n,m;//n钱,m总数
ll temp_v,temp_p,temp_kind;
cin>>n>>m;
for(ll i=;i<=m;i++)
{
cin>>temp_v>>temp_p>>temp_kind;
if(temp_kind==)//如果编号为0,则是物品
{
main_v[i]=temp_v;
main_vp[i]=temp_v*temp_p;
}
else//如果是附属品
{
belong_v[temp_kind][]++;//判断现在是第几个附件,用belong_v[temp_kind][0]来存
belong_v[ temp_kind ][ belong_v[temp_kind][] ] = temp_v;
belong_vp[ temp_kind ][ belong_v[temp_kind][] ] = temp_v*temp_p;
}
}
for(ll i=;i<=m;i++)
for(ll j=n;j>=main_v[i]&&main_v[i]!=;j--)//如果main_v[i]==0则说明这个位置放的是附件
{//如果没进入这个地方就是什么也没买
f[j]=max(f[j],f[j-main_v[i]]+main_vp[i]);//只买主件或者不买
//接下来不能用else if呀,因为是各种情况中的比较
if(j-main_v[i]-belong_v[i][]>=)//买主件和附件1
f[j]=max(f[j],f[j-main_v[i]-belong_v[i][]] + main_vp[i]+belong_vp[i][]);
if(j-main_v[i]-belong_v[i][]>=)//买主件和附件2
f[j]=max(f[j],f[j-main_v[i]-belong_v[i][]] + main_vp[i]+belong_vp[i][]);
if(j-main_v[i]-belong_v[i][]-belong_v[i][]>=)//买主件和附件1和附件2
f[j]=max(f[j],f[j-main_v[i]-belong_v[i][]-belong_v[i][]] + main_vp[i]+belong_vp[i][]+belong_vp[i][]);
}
cout<<f[n]<<endl;
}
金明的预算方案
四.我没想出来的原因
1.我第一种思路是,标记主件有没有被选,但是在动态规划中标记法是不可行的,而且最好不要回溯
2.我第二种思路是,先判断主件,再判断附件,可是这样没什么实际意义,因为主件会对后面的附件产生后效性
3.我一直的疑惑是:判断主件和附件1都有的时候算一种,那么判断主件和附件2都有的时候,怎么知道主件有没有被买过,其实这里就差一点了,只要再考虑同时被买就好了,因为最多才两个附件,其实这是有暗示的:最多两个附件,两个那么小的数字,只有四种情况,完全可以组合出来
4.看懂思路之后我还是WA了一次,错在细节,就是附件的下标应该用temp_kind而不是i,因为附件的下标是紧跟主件的,也就是他们之间要有一个东西,一条纽带能连接
5.又错了一个细节,就是我写了这样的东西f[j]=f[j-main_v[i]]+main_vp[i]这的意思是能买就一定买,是错的,应该是能买再考虑买不买