Solution :

990 - Diving for Gold

Solution :

#include < iostream > 
#include < stdio.h >
using namespace std;
#define INF 9999999
int N, G;
struct Data {
    int price;
    int weight;
}
dataArray[1001];
int dp[1001][1001];
void intData();
void initDP();
int knapsac(int, int, int);
int main() {
    int T, tc;
    freopen("10130.txt", "r", stdin);
    cin >> T;
    for (tc = 0; tc < T; tc++) {
        N = G = 0;
        cin >> N;
        intData();
        for (int i = 0; i < N; i++) {
            cin >> dataArray[i].price >> dataArray[i].weight;
        }
        cin >> G;
        int sum = 0;
        for (int j = 0; j < G; j++) {
            initDP();
            int maxCapPerPerson;
            cin >> maxCapPerPerson;
            sum += knapsac(0, 0, maxCapPerPerson);
        }
        cout << sum << endl;
    }
    return 0;
}
int knapsac(int level, int currentWeight, int maximumWeight) {
    if (dp[level][currentWeight] != INF) return dp[level][currentWeight];
    if (level == N) return 0;
    int takenValue, notTakenValue;
    if (currentWeight + dataArray[level].weight <= maximumWeight)
        takenValue = dataArray[level].price + knapsac(level + 1, currentWeight + dataArray[level].weight, maximumWeight);
    else takenValue = 0;
    notTakenValue = knapsac(level + 1, currentWeight, maximumWeight);
    dp[level][currentWeight] = (takenValue > notTakenValue ? takenValue : notTakenValue);
    return dp[level][currentWeight];
}
void initDP() {
    for (int i = 0; i < 1001; i++) {
        for (int j = 0; j < 1001; j++) {
            dp[i][j] = INF;
        }
    }
}
void intData() {
    for (int i = 0; i < 1001; i++) {
        dataArray[i].price = INF;
        dataArray[i].weight = INF;
    }
}