华为9月2号笔试第三题(货车搬家)是不是有问题

这题是标准的01背包问题没有任何变形,但是只能过80%
求教
int main() {
	int k, n;
	cin >> k >> n;
	vector<int> v;
	vector<int> w;
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		w.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	vector<int> dp(k + 1, 0);
	for (int j = 0; j < n; j++) {
		int tmpw = w[j];
		int val = v[j];
		for (int r = k; r >= tmpw; --r) {
			dp[r] = max(dp[r], dp[r - tmpw] + val);
		}
	}
	cout << *max_element(dp.begin(), dp.end()) << endl;
}


#笔试题目##华为#
全部评论
我也80
点赞
送花
回复
分享
发布于 2020-09-02 21:36
题目上说要在火车载货量最大的情况下求最大的价值,所以得先判断最大的载货量是多少(先dp一遍,判断哪些(载货量状态是可以到达的),dp数组初始化为false,dp[0][0]初始化为true,一遍dp完之后可以知道实际可以达到的最大载货量是多少,然后使用01背包判断刚好容量为最大载货量的最大价值是多少---这是后面想的思路,刚开始也没做出来
点赞
送花
回复
分享
发布于 2020-09-03 09:14
秋招专场
校招火热招聘中
官网直投

相关推荐

2 1 评论
分享
牛客网
牛客企业服务