【动态规划】01背包问题
今天小编闲的不行，就打开洛谷，随便一打卡就是大吉，还宜刷题。
正巧上午比赛时有一道背包问题，于是小编默默打开试炼场，瞅准了背包问题（别问我为什么），正所谓自知者明，小编也知道自己很水（建议看背包九讲），于是挑了三道题：
在写之前总得知道什么是背包问题吧，背包问题一般长这样：
题目：有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]);
具体怎么实现，看几道吧。
先看第一道：
这道题处于秒杀的行列，直接用刚才的方法，把钱数看成是容量，把重要程度*价格看成是价值就好了，直接写就行，代码奉上：
1 #include<iostream> 2 using namespace std; 3 long long cost[30000],w[30000],f[30000],ans; 4 int main() 5 { 6 long long n,m; 7 cin>>n>>m; 8 for(int i=1;i<=m;i++) 9 cin>>cost[i]>>w[i]; 10 for(int i=1;i<=m;i++) 11 for(int j=n;j>=cost[i];j--) 12 { 13 if(j>=w[i]) 14 f[j]=max(f[j],f[j-cost[i]]+w[i]*cost[i]); 15 } 16 cout<<f[n]; 17 return 0; 18 }
先来看一下采药，比上面的还简单：
把时间看成容量，就可以了，代码献上：
1 #include<iostream> 2 using namespace std; 3 int t,m,w[1000],cost[1000],f[1000]; 4 int main() 5 { 6 cin>>t>>m; 7 for(int i=1;i<=m;i++) 8 cin>>w[i]>>cost[i]; 9 for(int i=1;i<=m;i++) 10 for(int j=t;j>=w[i];j--) 11 { 12 f[j]=max(f[j],f[j-w[i]]+cost[i]); 13 } 14 cout<<f[t]; 15 16 return 0; 17 }
最后来看小A点菜：
这道题乍一看没思路，还按照刚才的思路：要么吃，要么不吃，吃有什么代价，什么回报呢？钱变少了，方案数变多了呗；不吃呢？还是原来的方案数。这样两种情况就出来了：
-
f[j-cost[i]]； -
f[j]；
【注意】情况有变，这一次就不那么简单了，因为选和不选是两种不同的方案数，题目求的是一共的方案数，所以不是max，不是min，而是+。
归根结底长这样：f[j]=f[j]+f[j-cost[i]];
这样代码就出来了，代码呈上：
1 #include<iostream> 2 using namespace std; 3 int n,m,cost[100000],f[10000]; 4 int main() 5 { 6 cin>>n>>m; 7 for(int i=1;i<=n;i++) 8 cin>>cost[i]; 9 f[0]=1; 10 for(int i=1;i<=n;i++) 11 for(int j=m;j>=cost[i];j--) 12 f[j]=f[j]+f[j-cost[i]]; 13 cout<<f[m]; 14 return 0; 15 }