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

发布时间:2023年12月20日

背包问题

例题一

有?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最多能够摘到多少颗花生。

1.gif

输入格式

第一行是一个整数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;

}

?

文章来源:https://blog.csdn.net/weixin_55939638/article/details/135038990
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。