布丁阿嬤的煩惱

itsa20161027-4-dp.knr-style.cpp

#include <iostream>
using namespace std;

int T, N, G, c, w, C[1000], W[1000];

int knapsak() {
    int dp[35] = {0};
    for (int i = 0; i < N; ++i)
        for (int j = w, k; (k = j - W[i]) >= 0; --j)
            dp[j] = max(dp[j], dp[k] + C[i]);
    return dp[w];
}

int main() {
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; ++i)
            cin >> C[i] >> W[i];
        
        c = 0;
        cin >> G;
        while(G-- && cin >> w)
            c += knapsak();
        
        cout << c << endl;
    }
    return 0;
}

itsa20161027-4-dp.ws-style.cpp

#include <iostream>
using namespace std;

int iT, iN, iG, iC, iW, iCs[1000], iWs[1000];
int i, j , k;

int knapsak()
{
int iDP[35] = {0};
for (i = 0; i < N; ++i)
    for (j = w; (k = j - iWs[i]) >= 0; --j)
        iDP[j] = max(iDP[j], iDP[k] + iCs[i]);
return iDP[w];
}

int main()
{
cin >> iT;
while (iT--)
    {
    cin >> iN;
    for (i = 0; i < iN; ++i)
        cin >> iCs[i] >> iWs[i];

    iC = 0;
    cin >> iG;
    while(iG-- && cin >> iW)
        iC += knapsak();

    cout << iC << endl;
    }
return 0;
}

itsa20161027-4.knr-style.cpp

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef vector<int>             Vec;
typedef pair<int, int>          Pair;
typedef vector<Pair>            PairVec;
typedef PairVec::const_iterator VecIt;
typedef map<int, int>           Map;

void GenProductsMap(Map &PM, VecIt const &first, VecIt const &last, int const maxW, int c, int w) {
    if (w > maxW) return;
    PM[w] = max(c, PM[w]);
    
    if (first == last) return;
    GenProductsMap(PM, first + 1, last, maxW, c               , w                ); // 不拿
    GenProductsMap(PM, first + 1, last, maxW, c + first->first, w + first->second); // 拿
}

void GenProductsMap(Map &PM, PairVec const &P, int const maxW) {
    GenProductsMap(PM, P.begin(), P.end(), maxW, 0, 0);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        
        PairVec Products(N);
        for (Pair &product: Products)
            cin >> product.first >> product.second; // 先 cost 後 weight
        
        int G;
        cin >> G;
        
        Vec Workers(G);
        for (int &worker: Workers)
            cin >> worker;
        
        Map ProductsMap; // PM[weight] = maxCost;
        GenProductsMap(ProductsMap, Products, *max_element(Workers.begin(), Workers.end()));
        
        int costTotal = 0;
        for (int const worker: Workers)
            costTotal += max_element(
                    ProductsMap.begin(), ProductsMap.upper_bound(worker), // 不超過 worker 的負重
                    [](Pair const &a, Pair const &b){ return a.second < b.second; } // 比較 cost
                )->second; // 拿 cost
        
        cout << costTotal << endl;
    }
    return 0;
}

itsa20161027-4.ws-style.cpp

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef vector<int>             Vec;
typedef pair<int, int>          Pair;
typedef vector<Pair>            PairVec;
typedef PairVec::const_iterator VecIt;
typedef map<int, int>           Map;

void GenProductsMap(Map &PM, VecIt const &first, VecIt const &last, int const iMaxW, int iC, int iW)
{
if (iW > iMaxW)
    return;
PM[iW] = max(iC, PM[iW]);

if (first == last)
    return;
GenProductsMap(PM, first + 1, last, iMaxW, iC               , iW                ); // 不拿
GenProductsMap(PM, first + 1, last, iMaxW, iC + first->first, iW + first->second); // 拿
}

void GenProductsMap(Map &PM, PairVec const &P, int const iMaxW)
{
GenProductsMap(PM, P.begin(), P.end(), iMaxW, 0, 0);
}

int main()
{
int iT, iN, iG, iCostTotal;
cin >> iT;
while (iT--)
    {
    cin >> iN;
    PairVec vProducts(iN);
    for (Pair &product: vProducts)
        cin >> product.first >> product.second; // 先 cost 後 weight

    cin >> iG;
    Vec vWorkers(iG);
    for (int &worker: vWorkers)
        cin >> worker;

    Map mProductsMap; // PM[weight] = maxCost;
    GenProductsMap(mProductsMap, vProducts, *max_element(vWorkers.begin(), vWorkers.end()));

    iCostTotal = 0;
    for (int const worker: vWorkers)
        iCostTotal += max_element(
                mProductsMap.begin(), mProductsMap.upper_bound(worker), // 不超過 worker 的負重
                [](Pair const &a, Pair const &b){ return a.second < b.second; } // 比較 cost
            )->second; // 拿 cost

    cout << iCostTotal << endl;
    }
return 0;
}