problem - bestSum

Question

#include <iostream>
#include <vector>
#include <optional>

using namespace std;

optional<vector<int>> dp[10000+5];
optional<vector<int>> bestSum(int targetSum,vector<int> numbers) {
    for (int i = 0; i <= targetSum; ++i) {
        dp[i] = nullopt;
    }
    dp[0] = {};

    for (int i = 0; i <= targetSum; ++i) {
        if (dp[i] != nullopt) {
            for (int num : numbers) {
                optional<vector<int>> combination = dp[i];
                if (!dp[i+num] || dp[i + num]->size() > combination->size()) {
                    dp[i + num] = combination;
                }
            }
        }
    }
    return dp[targetSum];
}

int main()
{
    optional<vector<int>> a = bestSum(7, { 5,3,4,7 });
    cout << a.has_value();
    /*for (int x : *a)
        cout << x << ' ';*/
}

Cześć napisałem program bestSum używając tabulacji, jednak wynik jest zły. Wiecie może co mogłem przeoczyć?

Comments

program bestSum

To... nic nikomu nie mówi ;)

A patrząc na kod - masz 10k vectorów, ale nigdy w ogóle nic do żadnego nie piszesz...?

---

To... nic nikomu nie mówi ;)

Mnie nie mówi, jestem ciekaw o co tu biega :)

Answer 1

A co ten program ma liczyć, co to jest target sum, a czym jest best sum??

Answer 2

Przydałby się jakikolwiek opis kodu i jego przeznaczenia, ale możemy zgadywać na ślepo:

for (int i = 0; i <= targetSum; ++i) {
    dp[i] = nullopt;
}
dp[0] = {}; // dp[0] = std::vector<int>{};

Wszystkim elementom tablicy dp ustawiasz wartość na std::nullopt. Następnie pierwszemu elementowi przypisujesz wartość domyślną dla std::optional, czyli znowu std::nullopt. Nie chciałeś przypadkiem utworzyć pustego vectora?

Skoro chcesz używać tabulacji to czy nie powinieneś wstawiać liczb z wektora numbers (lub używać ich w jakiś inny sposób zgodny z zadaniem)?

if (!dp[i + num] || dp[i + num]->size() > combination->size()) {
    dp[i + num] = combination;
    dp[i + num]->emplace_back(num);
}