今天小编闲的不行, 就打开洛谷, 随便一打卡就是大吉, 还宜刷题.
正巧上午比赛时有一道背包问题, 于是小编默默打开试炼场, 瞅准了背包问题(别问我为什么), 正所谓自知者明, 小编也知道自己很水(建议看背包九讲 https://www.kancloud.cn/kancloud/pack/70125 ), 于是挑了三道题:
在写之前总得知道什么是背包问题吧, 背包问题一般长这样:
题目: 有 N 件物品和一个容量为 V 的背包. 第 i 件物品的费用是 w[i], 价值是 value[i]. 求解将哪些物品装入背包可使价值总和最大.
那么如何解这种题目呢, 先定义一个数组 f[i][j]为当一共有 i 件物品, 背包容量为 j 时的最大价值. 然后就要找状态转移方程了, 小编以前总认为状态转移方程难写, 但是只要一项一项列出来就好了. 对于每一个物品, 无非就两种可能: 要么选, 要么不选. 那么先看选, 凡是总有回报和代价把, 选了之后代价是什么呢? 想一想, 是不是选了之后背包剩余容量就减少了; 那么回报呢? 当然是价值增加了呗. 但是不选就不一样了, 应为啥也没干, 最大价值和之前一样, 不增不减. 这不就出来了嘛, 两种情况如下:
选: f[i][j]=f[i-1][j-w[i]]+value[i];
不选: f[i][j]=f[i-1][j];
因为题目求的是最大价值, 所以两者中取大的就可以了, 得到以下状态转移方程:
f[i][j]=max(f[i-1][j-w[i]]+value[i],f[i-1][j]);
有没有发现什么, 我们用了二维数组, 虽然时间上已经难以优化, 但是空间上还是可以优化成一维数组的, 只要同时去掉 i 的那一个维度就可以了, 因为二维数组有太多不需要一直记录的, 直接不断更新一维数组 (滚动数组的方式) 就可以了, 更改如下:
f[j]=max(f[j-w[i]]+value[i],f[j]);
具体怎么实现, 看几道吧.
先看第一道:
这道题处于秒杀的行列, 直接用刚才的方法, 把钱数看成是容量, 把重要程度 * 价格看成是价值就好了, 直接写就行, 代码奉上:
- #include<iostream>
- using namespace std;
- long long cost[30000],w[30000],f[30000],ans;
- int main()
- {
- long long n,m;
- cin>>n>>m;
- for(int i=1;i<=m;i++)
- cin>>cost[i]>>w[i];
- for(int i=1;i<=m;i++)
- for(int j=n;j>=cost[i];j--)
- {
- if(j>=w[i])
- f[j]=max(f[j],f[j-cost[i]]+w[i]*cost[i]);
- }
- cout<<f[n];
- return 0;
- }
先来看一下采药, 比上面的还简单:
把时间看成容量, 就可以了, 代码献上:
- #include<iostream>
- using namespace std;
- int t,m,w[1000],cost[1000],f[1000];
- int main()
- {
- cin>>t>>m;
- for(int i=1;i<=m;i++)
- cin>>w[i]>>cost[i];
- for(int i=1;i<=m;i++)
- for(int j=t;j>=w[i];j--)
- {
- f[j]=max(f[j],f[j-w[i]]+cost[i]);
- }
- cout<<f[t];
- return 0;
- }
最后来看小 A 点菜:
这道题乍一看没思路, 还按照刚才的思路: 要么吃, 要么不吃, 吃有什么代价, 什么回报呢? 钱变少了, 方案数变多了呗; 不吃呢? 还是原来的方案数. 这样两种情况就出来了:
- f[j-cost[i]];
- f[j];
[注意] 情况有变, 这一次就不那么简单了, 因为选和不选是两种不同的方案数, 题目求的是一共的方案数, 所以不是 max, 不是 min, 而是 +.
归根结底长这样: f[j]=f[j]+f[j-cost[i]];
这样代码就出来了, 代码呈上:
- #include<iostream>
- using namespace std;
- int n,m,cost[100000],f[10000];
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- cin>>cost[i];
- f[0]=1;
- for(int i=1;i<=n;i++)
- for(int j=m;j>=cost[i];j--)
- f[j]=f[j]+f[j-cost[i]];
- cout<<f[m];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2998589.html