Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Backpack with recursion
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//Title of this code //g++ 4.8.2 #include <iostream> #include <vector> #include <set> struct pair { int size; int value; pair(int s, int v): size(s), value(v) {} }; struct retType { std::vector<int> arr; int best; }; retType maxPack(std::vector<pair> t, int backSize, std::set<int> usedPos = {}) { int best = 0; int pos = -1; std::vector<int> array; retType retVal; for (int i = 0; i < t.size(); ++i) { int size = t[i].size; int value = t[i].value; if (usedPos.find(i) == usedPos.end() && backSize - size >= 0) { std::set<int> tmpUsedPos = usedPos; tmpUsedPos.insert(i); retType ret = maxPack(t, backSize - size, tmpUsedPos); if (ret.best + value > best) { best = ret.best + value; array = ret.arr; pos = i; } } } if (pos > -1) array.push_back(pos); retVal.arr = array; retVal.best = best; return retVal; } int main() { std::vector<pair> stuff = {pair(2,3), pair(1,4), pair(2,5), pair(4,6), pair(3,3)}; int packSize = 5; retType rv = maxPack(stuff, packSize); std::cout << rv.best << std::endl; for (int i = 0; i < rv.arr.size(); ++i) std::cout << rv.arr[i] << " "; }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
Compilation time: 0.62 sec, absolute running time: 0.14 sec, cpu time: 0 sec, memory peak: 3 Mb, absolute service time: 0.77 sec
fork mode
|
history
|
discussion
12 2 1 0