题解 | #称砝码#
称砝码
https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
//01背包+滚动数组
//把所有数字都存成一维数组
//二维dp的含义是：第i个筹码进来时，是否可以到达j重量
//转滚动就只要把对重量j的遍历倒过来就可以了。
//然后因为二维dp需要多创建一行来存最终的结果，一维滚动就直接在第len-1行了，而二维dp在len行，循环的话对len的循环少一次
#include<iostream>
#include<vector>using namespace std;
int main(){
int n;
cin >> n;
if(n == 0){
cout << 1 << endl;
return 0;
}
vector<int> m(n,0),x(n,0);
for(int i = 0;i<n;++i)cin >> m[i];
for(int i = 0;i<n;++i)cin >> x[i];
//可以用一维dp去存
//先获取最大值
int maxval = 0;
for(int i = 0;i<n;++i)maxval+= m[i]*x[i];
vector<int> nums;
int len = 0;
for(int i = 0;i<n;++i){
for(int j = 1;j<=x[i];++j){
nums.emplace_back(m[i]);
}
len+=x[i];
}
//这是正常的二维dp
// vector<vector<bool>> dp(len+1,vector<bool>(maxval+1,false));
// dp[0][0] = true;
// dp[0][nums[0]] = true;
// for(int i = 1;i<len+1;++i){
// for(int k = 0;k<maxval+1;++k){
// dp[i][k] = dp[i-1][k];
// if(k-nums[i]>=0)dp[i][k] = dp[i][k]|dp[i-1][k-nums[i]];
// }
// }
// int count = 0;
// for(int k = 0;k<maxval+1;++k)if(dp[len][k] == true)++count;
// cout << count << endl;
//这是滚动一维dp
vector<bool> dp(maxval+1,false);
dp[0] = true;
dp[nums[0]] = true;
for(int i = 1;i<len;++i){
for(int k = maxval;k-nums[i]>=0;--k){
dp[k] = dp[k]|dp[k-nums[i]];
}
}
int count = 0;
for(int k = 0;k<maxval+1;++k)if(dp[k] == true)++count;
cout << count << endl;
return 0;
}
查看14道真题和解析
投递美团等公司10个岗位