/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm> // std::max
using namespace std;
int knapsack(vector<int> Values, vector<int> Weights, int LimitWeight)
{
int MaxValue = 0;
int itemLen = Weights.size();
// 定义与实始化DP状态
vector<vector<int>> stateDP(LimitWeight+1, vector<int>(itemLen+1));
// 限定重量从1开始
for(int w = 1; w <= LimitWeight; w++){
// 在限定重量为w的情况下,遍历数组获取最大值
for(int posIndex = 1; posIndex <= itemLen; posIndex++){
int selectValue = 0;
int skipValue = stateDP[w][posIndex -1];
int posWeight = Weights[posIndex -1];
int posValue = Values[posIndex -1];
if (w >= posWeight) {
selectValue = posValue + stateDP[w - posWeight][posIndex -1];
}
stateDP[w][posIndex] = max(skipValue, selectValue);
}
}
// 从状态中取出最大值
MaxValue = stateDP[LimitWeight][itemLen];
return MaxValue;
}
int main(){
vector<int> Values{10, 40, 30, 50};
vector<int> Weights{5, 4, 6, 3};
int LimitWeight = 10;
int maxValues = knapsack(Values, Weights, LimitWeight);
cout<<"maxValues:"<<maxValues;
}