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; } ``#百度笔试##百度##笔经#