怎么全是 模拟退火 啊,这明明是个 枚举子集 的板子题。
考虑 \(n \leq 16\) 二进制没错了。。
\(dt_i\) 表示 \(i\) 这个状态下 \(\max{t_j}\),\([\texttt{i\&(1<<j)}]\)
\(dw_i\) 表示 \(i\) 这个状态下
\(\sum w_j\),\([\texttt{i&(1<<j)}]\)
\(dp_i\) 表示 \(i\) 这个状态下的最少时间
时间复杂度 \(O(3^n)\)
空间复杂度 \(O(2^n)\)
#include <bits/stdc++.h>
#define rep(i , x , y) for(register int i = x ; i <= y ; i ++)
#define int long long
using namespace std ;
signed main() {
ios :: sync_with_stdio(false) ;
cin.tie(nullptr) ;
cout.tie(nullptr) ;
int W , n ;
cin >> W >> n ;
vector < int > t(n) , w(n) ;
for(int i = 0 ; i < n ; i ++)
cin >> t[i] >> w[i] ;
vector < int > dt(1 << n) , dw(1 << n) ;
for(int i = 0 ; i < 1 << n ; i ++) {
for(int j = 0 ; j < n ; j ++) {
if(i & (1 << j)) continue ;
dt[i | (1 << j)] = max(dt[i] , t[j]) ;
dw[i | (1 << j)] = dw[i] + w[j] ;
}
}
vector < int > dp(1 << n , 999) ;
dp[0] = 0 ;
for(int i = 1 ; i < 1 << n ; i ++) {
for(int j = i ; j ; j = (j - 1) & i)
if(dw[j] <= W) dp[i] = min(dp[i] , dt[j] + dp[i ^ j]) ;
}
cout << dp[(1 << n) - 1] << '\n' ;
return 0 ;
}