4

Food Problem

문제: n종의 음식, m종의 차를 드리겠습니다. 각 음식은 3가지 속성 에너지치 t, 부피 u, 수량 v가 있습니다.각 차마다 세 개의 속성치 용량 x, 가격 y, 수량 z가 있다.
문제는 최소한 p에너지의 요구에 도달할 수 있는 최소 비용이 얼마이고 50000보다 크면 TAT를 출력하는 것이다
분석: 두 번의 다중 가방 dp는 최소한 p에너지의 최소 부피를 dp로 만든 다음에 50000에서 소비한 다음에 dp로 부피를 낸다. 만족하기 전의 최소 부피에서 답을 찾는다.
왜 부피 dp로 비용을 내지 않습니까?수량급이 어느 정도인지 보시면 알맞은 상태를 골라서 복잡도를 줄여야 돼요. 233.
바이너리 최적화 기억 233
코드:

//
//  Created by TaoSama on 2015-09-25
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m, p;
int dp[60005];
//1: dp[i][j]:= i desert j energy's minimum size
//2: dp[i][j]:= i truck j cost's maximum size

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &n, &m, &p);

        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for(int i = 1; i <= n; ++i) {
            int w, v, c; scanf("%d%d%d", &w, &v, &c);
            for(int k = 1; c > 0; c -= k, k <<= 1) {
                int mul = min(k, c);
                for(int j = p + 100; j >= mul * w; --j)
                    dp[j] = min(dp[j], dp[j - mul * w] + mul * v);
            }
        }
        int V = INF;
        for(int i = p; i <= p + 100; ++i) V = min(V, dp[i]);
//      printf("V: %d
", V);

        memset(dp, 0, sizeof dp);
        int ans = INF;
        for(int i = 1; i <= m; ++i) {
            int v, w, c; scanf("%d%d%d", &v, &w, &c);
            for(int k = 1; c > 0; c -= k, k <<= 1) {
                int mul = min(k, c);
                for(int j = 50000; j >= mul * w; --j) {
                    dp[j] = max(dp[j], dp[j - mul * w] + mul * v);
                    if(dp[j] >= V) ans = min(ans, j);
                }
            }
        }
        if(ans == INF) puts("TAT");
        else printf("%d
", ans);
    }
    return 0;
}

Storage Keepers
제목: n<100개의 창고 m<=30개의 관리자가 있습니다. 관리자마다 능력치 P(다음 줄에 m개, 관리자마다 능력치를 표시)가 있습니다. 창고는 한 명의 관리자만 관리할 수 있습니다.그러나 모든 관리자는 k개의 창고를 관리할 수 있다(그러나 이 창고에 분배된 안전치는 p/k,k=0,1에 불과하다...매달 회사에서 관리원에게 임금을 주어야 한다. 고용된 관리자의 임금은 그들의 능력치 p와 각 창고의 안전치가 가장 높은 전제에서 임금 총액을 최소화해야 한다. 최대 안전치를 수출하고 가장 적은 비용을 수출해야 한다.
분석: 다중 가방과 유사한 dp상태 두 번 코드 보기 첫 번째 dp에서 안전값이 나왔고 두 번째 이 상태에서 최소한의 비용을 찾아 초기화에 주의하고 잘 생각해 보세요.
코드:

//
//  Created by TaoSama on 2015-08-12
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m, p[35];
int f[35][105], g[35][105];
//dp[i][j]:= i people look after j storages max safe, min wage

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d", &m, &n) == 2 && (n || m)) {
        for(int i = 1; i <= n; ++i) scanf("%d", p + i);

        memset(f, 0, sizeof f);
        f[0][0] = INF; //initialization is so difficult!
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j]; //zero exception
                for(int k = 1; k <= p[i] && k <= j; ++k)
                    f[i][j] = max(f[i][j], min(f[i - 1][j - k], p[i] / k));
            }
        }
        int L = f[n][m];
        if(!L) {printf("0 0
"); continue;}

        memset(g, 0x3f, sizeof g);
        g[0][0] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j <= m; ++j) {
                g[i][j] = g[i - 1][j];
                for(int k = 1; k <= p[i] && k <= j; ++k) {
                    int s = p[i] / k;  //at least
                    if(s >= f[n][m]) g[i][j] = min(g[i][j], g[i - 1][j - k] + p[i]);
                }
            }
        }
        int Y = g[n][m];
        printf("%d %d
", L, Y);
    }
    return 0;
}

The Fewest Coins
제목: 화폐의 종류수와 총 구매치를 제시하고 각 화폐의 가치와 수량을 제시한다.
사장님도 모든 종류의 화폐를 가지고 있지만 수량 제한이 없어요. 물건을 살 때 가치가 정해진 가치를 초과하면 사장님이 거슬러 줍니다.
최소한의 교류 화폐의 수량을 구하다
분석: 두 번 dp, 첫 번째 다중 가방에서 동전을 얼마나 썼는지 구하고 두 번째 완전 가방에서 동전을 얼마나 찾았는지 구하고 최소치를 구한다.
가장 중요한 것은 상계의 처리다.상계는 maxw*maxw+m(maxw 최대 액면가의 지폐), 즉 24400위안임을 알 수 있다.
증명서를 붙이다.
만약에 구매자의 지불 금액이 maxw*maxw+m보다 크면 즉시 지불하는 동전의 수량은 maxw보다 크다. 비둘기 바구니 원리에 따라 적어도 두 개는 maxw에 대한 모형의 값과 같다.
즉 이 부분의 동전은 더 적은 맥스로 대체할 수 있다는 것이다.증명이 끝나다.
진심으로 증명을 몰라도 괜찮아요. 결론을 기억하면 돼요. 진심으로 결론을 기억하고 싶지 않아도 돼요. 수조를 크게 만들면 돼요.
코드:

//
//
//
//  Created by TaoSama on 2015-03-30
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int n, t, dpp[25000], dpn[15000], c[105], v[105];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//	freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    cin >> n >> t;
    for(int i = 1; i <= n; ++i) cin >> v[i];
    for(int i = 1; i <= n; ++i) cin >> c[i];

    memset(dpp, 0x3f, sizeof dpp);
    dpp[0] = 0;
    for(int i = 1; i <= n; ++i) {
        int k = 1;
        while(c[i] > 0) {
            int t = min(c[i], k);
            for(int j = t + 120 * 120; j >= t * v[i]; --j)
                dpp[j] = min(dpp[j], dpp[j - t * v[i]] + t);
            c[i] -= k; k <<= 1;
        }
    }
    /*for(int i = 0; i <= t + 120 * 120; ++i)
        if(dpp[i] != INF) printf("dpp[%d]: %d
", i, dpp[i]);*/

    memset(dpn, 0x3f, sizeof dpn);
    dpn[0] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = v[i]; j <= 120 * 120; ++j)
            dpn[j] = min(dpn[j], dpn[j - v[i]] + 1);
    /*for(int i = 0; i <= 120 * 120; ++i)
        if(dpn[i] != INF) printf("dpn[%d]: %d
", i, dpn[i]);*/

    int ans = INF;
    for(int i = 0; i <= 120 * 120; ++i)
        ans = min(ans, dpp[t + i] + dpn[i]);

    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}