0-1 背包问题

template <typename T>
T knapSack(const std::vector<int>& v, const std::vector<T>& w, int V) {
    int n = (int) v.size();
    std::vector<T> dp(V + 1);
    for (int i = 0; i < n; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp.back();
}

最后更新: 2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
回到页面顶部