【算法刷题】每日打卡——动态规划（1）

背包问题

例题一

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

方法一：二维数组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
//v[]体积 w[]价值
int f[N][N],v[N],w[N];
int main(){
    //wm:最大容量
    int n,vm;
    cin>>n>>vm;
    for(int i =1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i =1;i<=n;i++){
        for(int j =0;j<=vm;j++){
            f[i][j] = f[i-1][j];
            if(j>=v[i])
            f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][vm];
    return 0;

}

方法二：一维数组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int main(){
    //wm:最大容量
    int n,vm,v,w;
    cin>>n>>vm;
  
    for(int i =1;i<=n;i++){
        cin>>v>>w;
        for(int j =vm;j>=v;j--){
          f[j]= max(f[j],f[j-v]+w);
        }
    }
    cout<<f[vm];
    return 0;

}

例题二

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100,
1≤R,C≤100,
0≤M≤1000

输入样例：

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例：

8
16

方法一：二维数组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
//f[][]：最终结果 w[][]：花生数量
int f[N][N],w[N][N];

int main(){
    int T,R,C;
    cin>>T;
    while(T--){
        cin>>R>>C;
        for(int i =1;i<=R;i++){
            for(int j=1;j<=C;j++){
                cin>>w[i][j];
            }
        }
        for(int i =1;i<=R;i++){
            for(int j =1;j<=C;j++){
                f[i][j] = max(f[i-1][j],f[i][j-1])+w[i][j];
            }
        }

        cout<<f[R][C]<<endl;
    }

    return 0;

}

方法一：一维数组

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],w;

int main(){
    int T,R,C;
    cin>>T;
    while(T--){
        cin>>R>>C;
//清除上次的影响
        memset(f,0,N);
        for(int i =1;i<=R;i++){
            for(int j=1;j<=C;j++){
                cin>>w;
                f[j] = max(f[j],f[j-1])+w;
            }
        }


        cout<<f[C]<<endl;
    }

    return 0;

}

例题三

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],a[N];

int main(){
    int n,res=0;
    cin>>n;


        for(int i =1;i<=n;i++){
            cin>>a[i];
            for(int j=i-1;j>=0;j--){
                if(a[i]>a[j])f[i] = max(f[j],f[i]);
        }
            f[i]++;
            res = max(res,f[i]);
    }
    cout<<res<<endl;
    return 0;

}