代码随想录算法训练营第四十一天| 卡码网第46题、416. 分割等和子集

本文主要是介绍代码随想录算法训练营第四十一天| 卡码网第46题、416. 分割等和子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

卡码网第46题

题目链接
文章讲解

#include<bits/stdc++.h>
using namespace std;int M, N;void slove() {vector<int> weight(M);vector<int> value(M);for (int i = 0; i < M; i++) cin >> weight[i];for (int i = 0; i < M; i++) cin >> value[i];// 定义dp数组，dp数组初始化vector<int> dp(N + 1, 0);// 遍历推导dp数组for (int i = 0; i < M; i++) { // 物品for (int j = N; j >= weight[i]; j--) { // 背包dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[N] << '\n';
}int main() {while (cin >> M >> N) slove();return 0;
}

416. 分割等和子集

题目链接
文章讲解

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int avg = 0;for (int i = 0; i < n; i++) avg += nums[i];if (avg % 2 == 1) return false;avg /= 2;vector<int> dp(avg + 1, 0);for (int i = 0; i < n; i++) {for (int j = avg; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[avg] == avg;}
};

这篇关于代码随想录算法训练营第四十一天| 卡码网第46题、416. 分割等和子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---