DP- Knapsack

Uva-p10130(2Darray).cpp

#include <iostream>
#include <string.h>
using namespace std;
int p[10009], w[10009];


int main()
{
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> p[i] >> w[i];
        int ans = 0;
        int g, mxw; cin >> g;
        while(g--){
            cin >> mxw;
            int dp[n + 1][mxw + 1];
            memset(dp, 0, sizeof dp);
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= mxw; j++){
                    if( w[i - 1] > j ) dp[i][j] = dp[i - 1][j];
                    else dp[i][j] = max( dp[i - 1][j], p[i - 1] + dp[i - 1][j - w[i - 1]] );
                }
            }
            ans += dp[n][mxw];
        }
        cout << ans << '\n';
    }

    return 0;
}

Uva-p10130.cpp

//author: Abdul Matin
#include <iostream>
#include <string.h>
using namespace std;
int* p;
int* w;
int dp[1100][35];
int n, g;

int knapsack(int elemNo, int currentW){
    if(elemNo == n + 1) return 0;
    if(dp[elemNo][currentW] != - 1) return dp[elemNo][currentW];
    if(currentW >= w[elemNo - 1])
        return dp[elemNo][currentW] = max( knapsack(elemNo + 1, currentW - w[elemNo - 1]) + p[elemNo - 1], knapsack(elemNo + 1, currentW));
    else return dp[elemNo][currentW] = knapsack(elemNo + 1, currentW);
}

int main()
{
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        p = new int[n], w = new int[n];
        
        for(int i = 0; i < n; i++)
            cin >> p[i] >> w[i];
        cin >> g;
        int tmp;
        int ans = 0;
        for(int i = 0; i < g; i++){
            memset(dp, -1, sizeof dp);
            cin >> tmp;
            ans += knapsack(1, tmp);
        }
        cout << ans << endl; 
        delete[] p;
        delete[] w;
    }

    return 0;
}