一.题目链接: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[32000+1]; ll main_v[60+1];//v主件单个价格 ll main_vp[60+1];//主件单个重要度p*价格v ll belong_v[60+1][3];//附件价格v ll belong_vp[60+1][3];//附件重要度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=1;i<=m;i++) { cin>>temp_v>>temp_p>>temp_kind; if(temp_kind==0)//如果编号为0,则是物品 { main_v[i]=temp_v; main_vp[i]=temp_v*temp_p; } else//如果是附属品 { belong_v[temp_kind][0]++;//判断现在是第几个附件,用belong_v[temp_kind][0]来存 belong_v[ temp_kind ][ belong_v[temp_kind][0] ] = temp_v; belong_vp[ temp_kind ][ belong_v[temp_kind][0] ] = temp_v*temp_p; } } for(ll i=1;i<=m;i++) for(ll j=n;j>=main_v[i]&&main_v[i]!=0;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]>=0)//买主件和附件1 f[j]=max(f[j],f[j-main_v[i]-belong_v[i][1]] + main_vp[i]+belong_vp[i][1]); if(j-main_v[i]-belong_v[i][2]>=0)//买主件和附件2 f[j]=max(f[j],f[j-main_v[i]-belong_v[i][2]] + main_vp[i]+belong_vp[i][2]); if(j-main_v[i]-belong_v[i][1]-belong_v[i][2]>=0)//买主件和附件1和附件2 f[j]=max(f[j],f[j-main_v[i]-belong_v[i][1]-belong_v[i][2]] + main_vp[i]+belong_vp[i][1]+belong_vp[i][2]); } 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]这的意思是能买就一定买,是错的,应该是能买再考虑买不买