今日任务
01背包问题
题目链接 : https://kamacoder.com/problempage.php?pid=1046题目描述 :
Code
# include <iostream>
# include <vector>
# include <functional>
# include <algorithm> using namespace std; int main ( void ) { int n, sz; cin >> n >> sz; vector< int > spaces ( n) ; vector< int > values ( n) ; for ( int i = 0 ; i < n; i++ ) { cin >> spaces[ i] ; } for ( int i = 0 ; i < n; i++ ) { cin >> values[ i] ; } vector< int > dp ( sz + 1 ) ; for ( int i = 0 ; i < n; i++ ) { int x = spaces[ i] , v = values[ i] ; for ( int c = sz; c >= x; c-- ) { dp[ c] = max ( dp[ c] , dp[ c - x] + v) ; } } cout << dp[ sz] << "\n" ; return 0 ;
}
416. 分割等和子集
题目链接 : https://leetcode.cn/problems/partition-equal-subset-sum/题目描述 :
Code
class Solution {
public : bool canPartition ( vector< int > & nums) { int sum = reduce ( nums. begin ( ) , nums. end ( ) , 0 ) ; if ( sum % 2 ) { return false ; } int t = sum / 2 ; int n = nums. size ( ) ; vector< bool > dp ( t + 1 ) ; dp[ 0 ] = true ; int pre = 0 ; for ( int x : nums) { pre = min ( pre + x, t) ; for ( int c = pre; c >= x; c-- ) { dp[ c] = dp[ c] || dp[ c - x] ; } } return dp[ t] ; }
} ;