三十五天打卡，背包问题入门，之前做过还是比较容易的
46.卡码网【携带研究材料】
题目链接
解题过程
- 采用二维bp，
bp[i][j]的含义是，背包容量为j，只装序号为0~i的物品时能装的最大价值 - 若背包容量大于等于当前物品的重量，可以选择装或者不装
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- 若背包容量小于当前物品的重量，只能选择不装
dp[i][j] = dp[i - 1][j];
二维dp
#include<iostream>
#include<vector>
using namespace std;
int main() {int m, n;cin >> m >> n;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];}vector<vector<int>>dp(m, vector<int>(n + 1));for (int j = weight[0]; j <= n; j++) {dp[0][j] = value[0];}for (int i = 1; i < m; i++) {for (int j = 0; j <= n; j++) {if (weight[i] <= j) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);} else {dp[i][j] = dp[i - 1][j];}}}cout << dp.back().back();return 0;}
解题过程
- 采用一维dp，
bp[j]的含义是，背包容量为j，能装物品的最大价值 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);- 倒序遍历是为了让所有物品只被放入一次
一维dp
#include<iostream>
#include<vector>
using namespace std;
int main() {int m, n;cin >> m >> n;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];}vector<int>dp(n + 1);for (int i = 0; i < m; i++) {for (int j = n; j >= 0; j--) {if (j >= weight[i]) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}}cout << dp.back();return 0;}
416.分割等和子集
题目链接
解题过程
- 采用背包问题解法，背包容量为
sum / 2，物品的重量和价值都为num[i]。 - 背包如果正好装满，说明找到了总和为
sum / 2的子集。 - 本题中我们要使用的是01背包，因为元素我们只能用一次。
- dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
01背包
class Solution {
public:bool canPartition(vector<int>& nums) {int target = 0;int sum = 0;for (int n : nums) sum += n;if (sum % 2 == 1) return false;target = sum / 2;vector<int>dp(target + 1);for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= 0; j--) {if (j >= nums[i]) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}}return dp.back() == target;}
};
