百度C++三面凉经

// 你必须定义一个 `main()` 函数入口。

// 题目[二进制求和]：给定两个二进制字符串，返回它们的和(用二进制表示)。输入a=11，b=1，输出100

// 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少。输入wt=[2,2,6,5,4]，value=[6,3,5,4,6]，W=10，输出15

#include <iostream>

#include <string>

#include <vector>

using namespace std;

//dp[i][j]=max(dp[i-1][j-wt[i]]+value[i] if j>=wt[i],dp[i-1][j])

//[1,2,3,4]

//[2,3,4,5]

//[1,2,4,5]

int getMaxValue(const vector<int>&wt,const vector<int>&value,int W){

if(wt.size()<1) return 0;

vector<int>dp(W+1);

for(int i=0;i<wt.size();++i){

for(int j=W;j>=0;--j){

if(j>wt[i])

dp[j]=max(dp[j-wt[i]]+value[i],dp[j]);

}

}

return dp.back();

}

string add(const string& num1,const string& num2){

int i=num1.length()-1;

int j=num2.length()-1;

string res="";

int carry=0;

while(i>=0||j>=0||carry>0){

if(i>=0) carry+=num1[i--]-'0';

if(j>=0) carry+=num2[j--]-'0';

res=(carry%2==1?"1":"0")+res;

carry/=2;

}

return res;

}

int main()

{

vector<int>wt={2,2,6,5,4};

vector<int>value={6,3,5,4,6};

cout<<getMaxValue(wt,value,10)<<endl;

return 0;

}