卡瑪網46：

問題描述：

小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實驗設備、文獻資料和實驗樣本等等，它們各自占據不同的空間，并且具有不同的價值。?

小明的行李空間為 N，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料只能選擇一次，并且只有選與不選兩種選擇，不能進行切割。

代碼及注釋解析：

#include<iostream>using namespace std;
//m個物品，背包容量最大為n
int m, n;
const int MAX_N = 5000;//滾動數組優化01背包問題
int dp[MAX_N + 1];//weight[i]代表第i個物品的重量
int weight[MAX_N];
//value[i]代表第i個物品的價值
int value[MAX_N];int main() {cin >> m >> n;for (int i = 0; i < m; i++) cin >> weight[i];for (int i = 0; i < m; i++) cin >> value[i];//外循環代表，對前i個物品進行放入找最優解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] << endl;return 0;
}

Leetcode416：

問題描述：

給你一個?只包含正整數?的?非空?數組?nums?。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

示例 1：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

輸入：nums = [1,2,3,5]
輸出：false
解釋：數組不能分割成兩個元素和相等的子集。

代碼及注釋解析：

class Solution {
public:int dp[10005];bool canPartition(vector<int>& nums) {int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}//總和為奇數不可能滿足題目要求if (sum % 2 == 1)return false;//找子集和為總和的一半值sum = sum / 2;//滾動數組求解for (int i = 0; i < nums.size(); i++) {for (int j = sum; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[sum] == sum;}
};