2021-9-7 百度算法笔试题

仅供交流，侵删

请大家评论区留言~

1、多重背包---->0-1背包

solve

/*
 * @Description: 百度9-7笔试
 * @Author: 
 * @Date: 2021-09-07 18:59:07
 * @LastEditTime: 2021-09-07 20:33:41
 * @LastEditors: maple
 */

#include "common.h"

void test1(vector<vector<int>>& mat, int money){
    int m = mat.size();

    vector<vector<int>> dp(m+1, vector<int>(money+1, 0));

    // init

    // dp
    for(int i = 1; i<m+1; i++){
        int weight = mat[i-1][0];
        int value = mat[i-1][1];
        for(int j = 1; j<money+1; j++){
            dp[i][j] = dp[i-1][j];
            if(j>=weight){
                dp[i][j] = max(dp[i][j], dp[i-1][j-weight]+value);
            }
        }
    }

    // debug
    // cout << "---debug---" << endl;
    // for(const auto& line:dp){
    //     for(const auto& ele:line){
    //         cout << ele << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "---" << endl;

    cout << dp[m][money] << endl;


}


int main(){

    int N, W;
    cin >> N >> W;
    vector<vector<int>> mat;
    for(int i = 0; i<N; i++){
        int a, b;
        cin >> a >> b;
        vector<int> tmp;
        tmp.push_back(a);
        tmp.push_back(b);
        mat.push_back(tmp);
    }
    vector<vector<int>> new_mat;

    for(const auto& line:mat){
        new_mat.push_back(line);
        new_mat.push_back(line);

    }


    // debug
    // cout << "--debug---" << endl;
    // for(const auto& line:new_mat){
    //     for(const auto& ele:line){
    //         cout << ele << " ";
    //     }
    //     cout << endl;
    // }

    test1(new_mat, W);



    return 0;
}

2、好像是一个矩阵路径问题

/*
 * @Description: 百度9-7笔试 第二题
 * @Author: 
 * @Date: 2021-09-07 18:59:07
 * @LastEditTime: 2021-09-07 21:27:45
 * @LastEditors: maple
 */


/*
    小明的店里准备了一些礼物，分为a，b两个品种。
    为了促销，小明希望把礼物进行组合后打包售卖。组合的方式包括两种，
    一种是组合里有x件a类礼物加y件b类礼物，一种是组合里有x件b类礼物加y件a类礼物。
    小明希望自己的组合数越多越好，你能告诉他他最多可以组多少个组合么？
*/
#include "common.h"




int main(){

    int a, b, x, y;
    cin >> a >> b >> x >> y;

    cout << a << ", " << b << ", " << x << ", " << y << endl;

    if(!((a>=x && b>=y) || (a>=y && b>=x))){
        return 0;
    }
    vector<vector<int>> dp(a+1, vector<int>(b+1, 0));
    for(int i = 0; i<=a; i++){
        for(int j = 0; j<=b; j++){
            if(!((i>=x && j>=y) || (i>=y && j>=x))){
                dp[i][j] = 0;
            }
            else if(i>=x && j>=y && i>=y && j>=x) {
                dp[i][j] = max(dp[i-x][j-y], dp[i-y][j-x])+1;
            }
            else if(i>=x && j>=y){
                dp[i][j] = dp[i-x][j-y]+1;
            }
            else{
                dp[i][j] = dp[i-y][j-x]+1;
            }
        }
    }

    // debug 
    cout << "---" << endl;
    for(const auto& line:dp){
        for(const auto& ele:line){
            cout << ele << " ";
        }
        cout << endl;
    }
    cout << "---" << endl;

    cout << dp[a][b] << endl;


    return 0;
}
``

#百度笔试##百度##笔经#