46. 攜帶研究材料（第六期模擬筆試）

題目描述

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

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

輸入描述

第一行包含兩個正整數，第一個整數 M 代表研究材料的種類，第二個正整數 N，代表小明的行李空間。

第二行包含 M 個正整數，代表每種研究材料的所占空間。?

第三行包含 M 個正整數，代表每種研究材料的價值。

輸出描述

輸出一個整數，代表小明能夠攜帶的研究材料的最大價值。

輸入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

輸出示例

5

#include<bits/stdc++.h>
using namespace std;int n,bagweight;void solvation()
{std::vector<int> weight(n,0);vector<int> value(n,0);for(int i = 0 ; i < n; i++){cin >> weight[i];}for(int i = 0 ; i < n ; i++){cin >> value[i];}vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));for(int i = weight[0] ; i <= bagweight ; i ++){dp[0][i] = value[0];}for(int i = 1; i < weight.size() ; i++){for(int j = 0; j <= bagweight ; j ++){if(weight[i] > j) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j],dp[i-1][j - weight[i]]+ value[i] );}}cout << dp[weight.size() - 1][bagweight];
}int main()
{while(cin >> n >> bagweight){solvation();}return 0 ;
}

滾動數組的寫法：

#include<bits/stdc++.h>
#include<vector>
using namespace std;int n ,bagweight;void solveproblem()
{std::vector<int> weight(n);vector<int> value(n);for(int i = 0; i < n; i++){cin >> weight[i];}for(int i = 0; i < n; i++){cin >> value[i];}vector<int> dp(bagweight+1,0);for(int i = 0 ; i < weight.size(); i++){for( int j = bagweight ; j >= weight[i] ; j--){if(j < weight[i]) dp[j] = dp[j-1];else dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);}//注意這里不是max(dp[j-1])}cout << dp[bagweight] <<endl;
}int main()
{while(cin >> n >> bagweight){solveproblem();}return 0 ;
}

416. 分割等和子集

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

示例 1：

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

示例 2：

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

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