Knapsack Bottom-Up

knap_bot-up.cpp

// Rogerio Junior
// March 18, 2017

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1010

int dp[MAXN][MAXN], w[MAXN], v[MAXN];

int main(){

    for(int caso=1;true;caso++){

        int c, f;
        cin >> c >> f;

        if(c==0 and f==0) break;

        for(int i=0;i<f;i++) cin >> w[i] >> v[i];

        for(int i=0;i<=c;i++) dp[f][i]=0;

        for(int k=f-1;k>=0;k--)
            for(int i=0;i<=c;i++){

                int nao_coloca=0, coloca=0;
                nao_coloca=dp[k+1][i];
                if(i>=w[k]) coloca=v[k]+dp[k+1][i-w[k]];

                dp[k][i]=max(coloca,nao_coloca);
            }

        cout << "Teste " << caso << "\n" << dp[0][c] << "\n\n";
    }

    return 0;
}