異なる金額のコインを積み重ねると、コインを上から出すことしか許されません。 n個のコインを家に持ち帰ることができると仮定すると、最大値は何ですか？

Question

上記は質問です。基本的に、入力はvector<stack<int>>& pilesとnであり、出力はすべての杭からのすべてのnコインの最大値です。

私が考えることができる唯一の解決策は、各パイルのためのバックトラック使用することである、すなわちpiles[0]を再帰的piles[1...m-1]とn - iに関数を呼び出す、iコインが選択されます。すべての可能な組み合わせの最大値を記録します。私はこれが動的プログラミングによって解決できるように感じますが、制約nのために、私はdp方程式を構築するのは難しいです。

バックトラッキングよりも優れたソリューションはありますか？

Answer 1

m個のファイルがあります。すべてのパイルpは、n個の0からnまでの (label, gain, cost)： のn + 1個の寄稿を提供します。("pile {p}, {i} taken", sum of top i values, i)です。

コストの合計は、n（利得が最大）に等しい（または負数の場合は少ない）必要があります。

残りはアルゴリズムに従います：降順で並べ替えるかどうかは((double)gain)/costなどです。

Answer 2

これは確かにnHrの組み合わせです。 私はこのようないくつかのコードを使用します。p =パイルの数、n =コインの数です。 calc_sumは最大値を記録する関数です。

nHr h(p, n); 
while(h.next()) { 
    for(int i=0; i<h.size(); i++) take_coins_from_a_pile(h[i]); 
    calc_sum(); 
} 

これは私自身のnHrライブラリです。

#pragma once 
#include <exception> 

class NRexception : public std::exception 
{ 
public: 
    virtual const char* what() const throw() { 
     return "Combination : N, R should be positive integer!!"; 
    } 
}; 

class Combination 
{ 
public: 
    Combination(int n, int r); 
    virtual ~Combination() { delete [] ar;} 
    int& operator[](unsigned i) {return ar[i];} 
    bool next(); 
    int size() {return r;} 
    static int factorial(int n); 

protected: 
    int* ar; 
    int n, r; 
}; 

class nCr : public Combination 
{ 
public: 
    nCr(int n, int r); 
    bool next(); 
    int count() const; 
}; 

class nTr : public Combination 
{ 
public: 
    nTr(int n, int r); 
    bool next(); 
    int count() const; 
}; 

class nHr : public nTr 
{ 
public: 
    nHr(int n, int r) : nTr(n,r) {} 
    bool next(); 
    int count() const; 
}; 

class nPr : public Combination 
{ 
public: 
    nPr(int n, int r); 
    virtual ~nPr() {delete [] on;} 
    bool next(); 
    void rewind(); 
    int count() const; 

private: 
    bool* on; 
    void inc_ar(int i); 
}; 

#include "combi.h" 
#include <set> 
#include<cmath> 

Combination::Combination(int n, int r) 
{ 
    //if(n < 1 || r < 1) throw NRexception(); 
    ar = new int[r]; 
    this->n = n; 
    this->r = r; 
} 

int Combination::factorial(int n) 
{ 
    return n == 1 ? n : n * factorial(n-1); 
} 

int nPr::count() const 
{ 
    return factorial(n)/factorial(n-r); 
} 

int nCr::count() const 
{ 
    return factorial(n)/factorial(n-r)/factorial(r); 
} 

int nTr::count() const 
{ 
    return pow(n, r); 
} 

int nHr::count() const 
{ 
    return factorial(n+r-1)/factorial(n-1)/factorial(r); 
} 

nCr::nCr(int n, int r) : Combination(n, r) 
{ 
    if(r == 0) return; 
    for(int i=0; i<r-1; i++) ar[i] = i + 1; 
    ar[r-1] = r-1; 
} 

nTr::nTr(int n, int r) : Combination(n, r) 
{ 
    for(int i=0; i<r-1; i++) ar[i] = 1; 
    ar[r-1] = 0; 
} 

bool nCr::next() 
{ 
    if(r == 0) return false; 
    ar[r-1]++; 
    int i = r-1; 
    while(ar[i] == n-r+2+i) { 
     if(--i == -1) return false; 
     ar[i]++; 
    } 
    while(i < r-1) ar[i+1] = ar[i++] + 1; 
    return true; 
} 

bool nTr::next() 
{ 
    ar[r-1]++; 
    int i = r-1; 
    while(ar[i] == n+1) { 
     ar[i] = 1; 
     if(--i == -1) return false; 
     ar[i]++; 
    } 
    return true; 
} 

bool nHr::next() 
{ 
    ar[r-1]++; 
    int i = r-1; 
    while(ar[i] == n+1) { 
     if(--i == -1) return false; 
     ar[i]++; 
    } 
    while(i < r-1) ar[i+1] = ar[i++]; 
    return true; 
} 

nPr::nPr(int n, int r) : Combination(n, r) 
{ 
    on = new bool[n+2]; 
    for(int i=0; i<n+2; i++) on[i] = false; 
    for(int i=0; i<r; i++) { 
     ar[i] = i + 1; 
     on[i] = true; 
    } 
    ar[r-1] = 0; 
} 

void nPr::rewind() 
{ 
    for(int i=0; i<r; i++) { 
     ar[i] = i + 1; 
     on[i] = true; 
    } 
    ar[r-1] = 0; 
} 

bool nPr::next() 
{ 
    inc_ar(r-1); 

    int i = r-1; 
    while(ar[i] == n+1) { 
     if(--i == -1) return false; 
     inc_ar(i); 
    } 
    while(i < r-1) { 
     ar[++i] = 0; 
     inc_ar(i); 
    } 
    return true; 
} 

void nPr::inc_ar(int i) 
{ 
    on[ar[i]] = false; 
    while(on[++ar[i]]); 
    if(ar[i] != n+1) on[ar[i]] = true; 
}