需要烹饪n道菜,第i道菜耗时t[i],有两个相同的烤箱,一个烤箱同一时间只能烹饪同一道菜。求烹饪完所有菜所需的最短时间?
1<=n<=100, 1<=t[i]<=1000

01背包变形,需要选出部分菜用烤箱1,其他用烤箱2,两者的最大值为结果,取所有可能的结果的最小值,即为答案。这里dp[i]表示总耗时为i的方案是否可行。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

const int N = 100000;
int n, a[101], dp[N+1], tot;
void solve() {
    cin >> n;
    rep(i,1,n) cin >> a[i], tot += a[i];
    dp[0] = 1;
    rep(i,1,n) per(j,a[i],N) {
        dp[j] |= dp[j-a[i]];
    }
    int ans = 1E8;
    rep(i,1,N) if (dp[i]) ans = min(ans, max(i, tot-i));
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。