Knapsack.cpp

//Copyright [2018] [Haibo Yan]
//
//Licensed under the Apache License, Version 2.0 (the "License");
//you may not use this file except in compliance with the License.
//You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
//Unless required by applicable law or agreed to in writing, software
//distributed under the License is distributed on an "AS IS" BASIS,
//WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//See the License for the specific language governing permissions and
//limitations under the License.

//
// Created by haibo on 3/27/18.
//

#include "Knapsack.h"
#include <climits>

using namespace std;

int Knapsack::valuable(int total) {
    int dp[total + 1];
    fill_n(dp, total + 1, 0);

    for (int i = 1; i <= total; i++) {
        int m = INT_MIN;

        for (auto ii = items_.begin(); ii != items_.end(); ii++) {
            int w = get<0>(*ii);
            int v = get<1>(*ii);

            if (w <= i) {
                m = max(m, dp[i - w] + v);
            }

        }
        dp[i] = m;
    }

    return dp[total];
}