动态规划

一.动态规划初步

 1.硬币问题 

B3635 硬币问题

需要依次枚举每种硬币能否应用的最大情况，设定用0个硬币时的初始值和一个硬币时的初始值（防止越界），后依次增加每个方案数；

#include<bits/stdc++.h>
using namespace std;
long long dp[10000005];
int main(){
    int n;
    cin>>n;
    dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=3,dp[4]=4,dp[5]=1,dp[6]=2,dp[7]=3,dp[8]=4,dp[9]=5,dp[10]=2,dp[11]=1;
    for(int i=11;i<=n;i++){
        dp[i]=min(min(dp[i-1],dp[i-5]),dp[i-11])+1;//最后加上现在的一个方案
    }
    cout<<dp[n];
    return 0;
}

题面：

二.01背包问题

推荐博文---【动态规划】01背包问题 - 弗兰克的猫 - 博客园 (cnblogs.com)

01背包上手题：P2871 [USACO07DEC] Charm Bracelet S (https://www.luogu.com.cn/problem/P2871)

改编版训练（初步）: P2392 kkksc03考前临时抱佛脚

思路：分别枚举左右脑计算每一科的最小时间（最大一次完成量），即所用时长应为总时长一半，且时长不小于每一道题应用时长。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int x[5],y[1000],num,ans,dp[1000];//x存储每一个学科，y存储每道题的时间
 4 //num表示总时间 ,ans是答案，dp数组存储每一科目所用最大时间 
 5 int main(){
 6     for(int i=1;i<=4;i++){//读入每一科 
 7         cin>>x[i];
 8     }
 9     for(int i=1;i<=4;i++){
10         num=0;
11         for(int j=1;j<=x[i];j++){
12             cin>>y[j];
13             num+=y[j];    //累加 
14         }
15         for(int j=1;j<=x[i];j++){    
16             for(int k=num/2;k>=y[j];k--){//两半脑子，所用时间最大为总时长一半 
17                 dp[k]=max(dp[k],dp[k-y[j]]+y[j]);//且不低于每题所用时间 
18             }//取每次最大所用度 
19         }
20         ans+=num-dp[num/2];//每次最少时间为总时间减去一半的最大时间 
21         memset(dp,0,sizeof dp);
22     }
23     cout<<ans;
24     return 0;
25 }

 改编版（背包问题)：P1164 小A点菜

本题与普通背包问题不同的是普通背包问题需要求最优解，此题求共有的方案数。

本题需要考虑三个条件：

1.当前剩余钱数刚好等于当前菜价，直接将方案数加1；

2.当前剩余钱数大于当前菜价，方案总数等于不买这道菜的方案数和买这道菜的方案数之和；

3.当前剩余钱数小于菜价，直接继承上一位的总方案数；

综上，可以设一个dp二维数组，代表前i道菜剩余j元时的方案数。

则代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1000],dp[10000][10000];
 4 int main(){
 5     int n,m;
 6     cin>>n>>m;
 7     for(int i=1;i<=n;i++)cin>>a[i];
 8     for(int i=1;i<=n;i++){//依次枚举每道菜的方案数 
 9         for(int j=1;j<=m;j++){//当前剩余总钱数，不管多大也不会超过m 
10             if(j==a[i])dp[i][j]=dp[i-1][j]+1;
11             if(j>a[i])dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
12             if(j<a[i])dp[i][j]=dp[i-1][j];
13         }
14     }
15     cout<<dp[n][m];//输出买n道菜时用m元的方案总数 
16 return 0;
17 }

 例二：（背包问题）P1802 5 倍经验日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先，看见此题应该直接判断出两种情况并同时列出转移方程：

1.打得过   1.打  dp[ j ] = dp[ j - use[ i ] + win[ i ] ];

　　　　   2.不打  dp[ j ] = dp[ j ] + lose[ i ];

2.打不过  dp[ j ] = lose[ i ];

因此，打得过的情况下 j 应大于此时所消耗的 use[ i ] ,反之则小于；

代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,x,lose[1005],win[1005],use[1005],dp[1005];
 4 int main(){ 
 5     cin>>n>>x;
 6     for(int i=1;i<=n;i++){
 7         cin>>lose[i]>>win[i]>>use[i];
 8         for(int j=x;j>=use[i];j--){//打得过时
 9             dp[j]=max(dp[j]+lose[i],dp[j-use[i]]+win[i]);//取打和不打的最大值（所获经验最大）
10         }
11         for(int j=use[i]-1;j>=0;j--)dp[j]+=lose[i];//打不过的情况
12     }
13     cout<<dp[x]*5;//五倍经验
14 
15 return 0;
16 }

 例三：01背包经典题目：P3273 - TBOJ-J1T2【小花园美化计划】 - TBOJ

　两个方案：1 . 买  1   dp [ j ] = max ( dp [ j ] , dp [ j - v [ j ][ 0 ] ] + b [ i ] ) ;

　　　　　　2 . 买  2   同上仅是把0换成一

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int m,n,s,b[10005][100],v[10005][100],dp[10005],l;
 4 int main(){
 5     freopen("flower.in","r",stdin);
 6     freopen("flower.out","w",stdout);
 7     ios::sync_with_stdio(0);
 8     cin>>m>>n>>s;
 9     for(int i=1;i<=n;i++){
10         for(int j=1;j<=2;j++){
11             cin>>b[i][j]>>v[i][j];
12         }
13     }
14     for(int i=1;i<=n;i++){
15         for(int j=m;j>=0;j--){//枚举第i盆花用m元时漂亮指数
16             if(j>=v[i][1])dp[j]=max(dp[j],dp[j-v[i][1]]+b[i][1]);
17             if(j>=v[i][2])dp[j]=max(dp[j],dp[j-v[i][2]]+b[i][2]);
18         }
19     }
20     cout<<dp[m]+s;
21     return 0;
22 }

    方法：枚举 n 盆花的同时，枚举 m 元钱时各自的方案

三.完全背包问题

性质：与 01 背包一样，不过需要多次判断，重点还是找对转移方程

推荐博文：【动态规划】完全背包问题 - 弗兰克的猫 - 博客园 (cnblogs.com)

入门中。。。。

任务一： 将01背包改为完全背包！

修改方法：1.找出区别：一个可以重复选择多个，一个不可以。

·　　　　  2.转移公式如果选择多个需要加上乘号。

此法缺点：三重循环，时间复杂度炒鸡大！

代码ing~~：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long tim,num,dp[10005000],t[10005000],v[10005000];
 4 int main(){
 5     cin>>tim>>num;
 6     for(int i=1;i<=num;i++)
 7         cin>>t[i]>>v[i];
 8     for(long long i=1;i<=num;i++)
 9         for(long long j=tim;j>=1;j--){
10             for(long long k=0;k<=j/t[i];k++){//注意是j/t[i] 因为时间总量要跟着上面循环的变化而变化 
11                 dp[j]=max(dp[j],dp[j-k*t[i]]+k*v[i]);//注意 t[i]和v[i]要用k倍的 
12             }
13         }
14     
15     cout<<dp[tim];
16 return 0;
17 }

注：原题（会炸！）：P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 四.多重背包

性质：与完全背包相同，不过每一种物品限定个数（非无限）

本段重点！----自上而下记忆法（用来寻找转移方程）

特殊点：完全背包是与自身横向一行与纵向一列的总数和

 这两个背包问题的关键都在于状态转移方程的寻找，如果对于类似的问题没有思路，可以先尝试找出递归解法，然后自上而下的记忆法便水到渠成了。