9.19小米笔试
第一题用0-1背包的思想,但是一直只能过64% ,好想知道为什么
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
bool isValid (vector<int>& weight, int bagSize, int q) {
int len = weight.size();
vector<vector<bool>> dp(len + 1, vector<bool>(bagSize + 1, false));
dp[0][0] = true;
bool flag = false;
for (int i = 1; i < len; ++i) {
for (int j = 0; j <= bagSize; ++j) {
if (j < weight[i-1]) dp[i][j] = dp[i-1][j];
else if (j == weight[i-1]) dp[i][j] = true;
else if (weight[i-1] < j && weight[i-1] + q >= j) dp[i][j] = true;
else dp[i][j] = dp[i-1][j - weight[i-1]];
if (j == bagSize && dp[i][j]) return true;
}
}
return dp[len][bagSize];
}
int main(void)
{
int t;
cin >> t;
while (t--) {
int bagSize, n, q;
cin >> bagSize >> n >> q;
vector<int> weight(n);
for (int i = 0; i < n; ++i) cin >> weight[i];
if (isValid(weight, bagSize, q)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
bool isValid (vector<int>& weight, int bagSize, int q) {
int len = weight.size();
vector<vector<bool>> dp(len + 1, vector<bool>(bagSize + 1, false));
dp[0][0] = true;
bool flag = false;
for (int i = 1; i < len; ++i) {
for (int j = 0; j <= bagSize; ++j) {
if (j < weight[i-1]) dp[i][j] = dp[i-1][j];
else if (j == weight[i-1]) dp[i][j] = true;
else if (weight[i-1] < j && weight[i-1] + q >= j) dp[i][j] = true;
else dp[i][j] = dp[i-1][j - weight[i-1]];
if (j == bagSize && dp[i][j]) return true;
}
}
return dp[len][bagSize];
}
int main(void)
{
int t;
cin >> t;
while (t--) {
int bagSize, n, q;
cin >> bagSize >> n >> q;
vector<int> weight(n);
for (int i = 0; i < n; ++i) cin >> weight[i];
if (isValid(weight, bagSize, q)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
全部评论
相关推荐