NP Complete Menu Problem Program

[Labdabeta]

Hello. I was reading http://xkcd.com/287/ while bored and thus decided to write a program that would solve such np complete problems. Here is what I got:

#include <iostream>
#include <vector>
using namespace std;
template <typename T>
T NPMenuProblem(T desired, vector<T> options, vector<T> &ret)
{
    vector<T> save=ret;
    T remainder;
    T min=desired;
    vector<T> minsol;
    for (int i=0; i<options.size(); ++i)
    {
        ret=save;
        if (desired-options[i]>0.0)
        {
            ret.push_back(options[i]);
            remainder=NPMenuProblem(desired-options[i],options,ret);
            if (remainder==0)
                return 0;
            else if (remainder<min)
            {
                minsol=ret;
                min=remainder;
            }
        }
    }
    ret=minsol;
    return min;
}
int main()
{
    vector<int> opts;
    opts.push_back(215);
    opts.push_back(275);
    opts.push_back(335);
    opts.push_back(355);
    opts.push_back(420);
    opts.push_back(580);
    vector<int> ret;
    int des=1505;
    int rem=NPMenuProblem(des,opts,ret);
    for (int i=0; i<ret.size(); ++i)
        cout<<ret[i]<<" + ";
    cout<<" = "<<des<<" - "<<rem<<endl;
    return 0;
}

The issue is that it doesn't work and I cannot figure out why... any advice?

[phorce]

[removed]

[Labdabeta]

No NP-complete problems are not unsolveable... its just that they are unsolveable in POLYNOMIAL time (IE there is no n such that their solution has worst case time complexity of O(x^n) where x is the number of elements in the problem). My solution is definately NOT polynomial (its a simple depth-first search which runs in a^b where a is the depth of the tree (how many prices added together are less than the total) and b is the number of elements (how many prices)) this is exponential time (O(n^x)) which is far worse than polynomial time. My solution can be expressed in pseudo-code as:

function DFS(desired,choices)
    best_solution=worst possible solution
    for each choice in choices
        temp_solution=DFS(desired-choice,choices)+choice //this is simple appending
        if temp_solution is better than best_solution
            best_solution=temp_solution
    return best_solution

Of course since c++ requires a little more work this simple solution gets morphed a little. Nonetheless here is my code, rewritten with the pseudo-code comments next to it:

#include <iostream>
#include <vector>
using namespace std;
template <typename T>//function DFS(desired,choices=options,ret to hold current)
T NPMenuProblem(T desired, vector<T> options, vector<T> &ret)
{
    vector<T> save=ret;
    T remainder;
    //you can consider the next two variables as best_solution 
    T min=desired;//best solution has leftover of desired (this is okay, though
                  //                                            not obviously!)
    vector<T> minsol;//this stores the DFS()+choice part
    for (int i=0; i<options.size(); ++i)
    {
        ret=save;//reset the return parameter
        if (desired-options[i]>0.0)//stop searching after invalid value
        {
            ret.push_back(options[i]);//append the current option (+choice)
            //this sorta ends up becoming DFS()+choice
            remainder=NPMenuProblem(desired-options[i],options,ret);
            if (remainder==0)//we win! and ret is already modified! YAY!!!
                return 0;
            else if (remainder<min)//still a better solution though
            {
                minsol=ret;
                min=remainder;
            }
            //no else needed... we dont care if we got a worse solution!
        }
    }
    //this is return best_solution
    ret=minsol;
    return min;
}
int main()
{
    vector<int> opts;
    opts.push_back(215);
    opts.push_back(275);
    opts.push_back(335);
    opts.push_back(355);
    opts.push_back(420);
    opts.push_back(580);
    vector<int> ret;
    int des=1505;
    int rem=NPMenuProblem(des,opts,ret);
    for (int i=0; i<ret.size(); ++i)
        cout<<ret[i]<<" + ";
    cout<<" = "<<des<<" - "<<rem<<endl;
    return 0;
}

[sepp2k]

if (desired-options[i]>0.0)

You never check whether desired - options[i] == 0. You should push the item on the vector and return 0 in that case.

PS: Is there a specific reason that you're using 0.0 and not just 0? I realize you want the code to work with all types of numbers, but, unless I'm missing something, that would still be the case when using 0 and using 0 would avoid unnecessary conversions to double.

No NP-complete problems are not unsolveable... its just that they are unsolveable in POLYNOMIAL time

Unless P=NP.

[Labdabeta]

ok thanks! It works now (although the output is odd due to the additional + sign).

[Labdabeta]

Oops... I rushed to the mark as solved button too fast. The program worked fine while there was a valid solution (7*215=1505) but failed when that line was commented out. Any ideas on why?

#include <iostream>
#include <vector>
using namespace std;
template <typename T>//function DFS(desired,choices=options,ret to hold current)
T NPMenuProblem(T desired, vector<T> options, vector<T> &ret)
{
    vector<T> save=ret;
    T remainder;
    //you can consider the next two variables as best_solution
    T min=desired;//best solution has leftover of desired (this is okay, though
                  //                                            not obviously!)
    vector<T> minsol;//this stores the DFS()+choice part
    for (int i=0; i<options.size(); ++i)
    {
        ret=save;//reset the return parameter
        if (desired-options[i]>0.0)//stop searching after invalid value
        {
            ret.push_back(options[i]);//append the current option (+choice)
            //this sorta ends up becoming DFS()+choice
            remainder=NPMenuProblem(desired-options[i],options,ret);
            if (remainder==0)//we win! and ret is already modified! YAY!!!
                return 0;
            else if (remainder<min)//still a better solution though
            {
                minsol=ret;
                min=remainder;
            }
            //no else needed... we dont care if we got a worse solution!
        }
        else if (desired-options[i]==0.0)
        {
            ret.push_back(options[i]);
            return 0;
        }
    }
    //this is return best_solution
    ret=minsol;
    return min;
}
int main()
{
    vector<int> opts;
    //opts.push_back(215);
    opts.push_back(275);
    opts.push_back(335);
    opts.push_back(355);
    opts.push_back(420);
    opts.push_back(580);
    vector<int> ret;
    int des=1505;
    int rem=NPMenuProblem(des,opts,ret);
    for (int i=0; i<ret.size()-1; ++i)
        cout<<ret[i]<<" + ";
    cout<<ret[ret.size()-1]<<" ";
    cout<<" = "<<des<<" - "<<rem<<endl;
    return 0;
}

[sepp2k]

You set ret to minsol even if minsol was never assigned in the loop. This means that when you reach a point where all items in the list cost more money than you have (which will happen eventually if no perfect solution is found), ret will be set to an empty vector.

You should only set ret to minsol if minsol has been assigned to at least once (or you could initialize minsol to ret, which would have the same effect and would be somewhat analogous to initializing min to desired).

PS: In the future it would be nice if you explained in what way your program failed (i.e. "the part of the output on the left side of the equals sign is empty, but the right side is correct") instead of just saying that it failed. That way I wouldn't have to copy your code onto my machine, compile and run it just to see what the problem is.

[Labdabeta]

Thank you, and sorry about the poor re-post. I will try to do better.