OnlineGDB

online compiler and debugger for c/c++

code. compile. run. debug. share.

Language

main.cpp

/****************************************************************************** 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; }

close ad [x]

Compiling Program...

Command line arguments:

Standard Input: Interactive Console Text

Program is not being debugged. Click "Debug" button to start program in debug mode.

Call Stack

#	Function	File:Line

Local Variables

Variable	Value

Registers

Register	Value

Display Expressions

Expression	Value

Breakpoints and Watchpoints

	#	Description