#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    1
    Rep Power
    0

    Please help me in this code


    There is a defect in the draft, but I do not know where you please help me
    #include <vector.h>
    #include <iostream.h>
    #include <iomanip.h>
    #include <string.h>

    struct item {
    int value;
    int capacity;
    };

    class Knapsack {
    public:
    Knapsack(int knapsack_size, int item_size);
    ~Knapsack();
    void add_items(int value, int capacity);
    int solve();
    void get_items_selected(std::vector<item>& resultItems);

    friend std::ostream &operator <<( std::ostream&, const Knapsack& );
    private:
    void init_knapsack_table();
    std::vector<item> m_items;
    int m_knapsack_size;
    int m_item_size;
    // 2D matrix to store intermediate
    // result of the knapsack calculation.
    std::vector<std::vector<int> > m_knapsack_table;
    // 2D matrix to store the intermediate
    // result for which item is selected
    // Later this matrix is used to get which items
    // are selected for optimal calculation.
    std::vector<std::vector<int> > m_selection_table;
    protected:
    };

    Knapsack::Knapsack(int knapsack_size, int item_size):
    m_knapsack_size(knapsack_size),
    m_item_size(item_size),
    m_knapsack_table(item_size + 1,std::vector<int>(knapsack_size + 1)),
    m_selection_table(item_size + 1,std::vector<int>(knapsack_size + 1)){
    m_items.reserve(m_item_size);
    }
    void Knapsack::add_items(int value, int capacity) {
    item t;
    t.value = value;
    t.capacity = capacity;
    m_items.push_back(t);
    }
    int Knapsack::solve() {
    // Initialize the first row in both the
    // tables, these values are used as default
    // as if no items are selected and no capacity
    // is available.
    // This is the default case for bottom-up approach.
    for ( int i = 0; i < m_knapsack_size + 1 ; i++) {
    m_knapsack_table [0][i] = 0;
    m_selection_table[0][i] = 0;
    }
    int row = 1;
    for ( std::vector<item>::iterator itemIterator = m_items.begin();
    itemIterator != m_items.end();
    ++itemIterator) {
    item currentItem = *itemIterator;
    int col = 0; // col is capacity available.
    while ( col < m_knapsack_size + 1 ) {
    //1. Check if item can be fit by it's own.
    if ( currentItem.capacity > col ) {
    //2. Get the solution for the already solved
    // knapsack problem.
    m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
    // Update the selection table as we are not able to accomodate this item
    // eventually we are not selecting this ite.
    m_selection_table[row][col] = 0;
    } else {
    // We are now considering the item.
    int capacity_remaining = col - currentItem.capacity;
    int new_value = currentItem.value + m_knapsack_table[row - 1][capacity_remaining];
    int prev_value = m_knapsack_table[row - 1][col];
    if ( prev_value >= new_value) {
    // There is no gain here to consider this item.
    m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
    m_selection_table[row][col] = 0;
    } else {
    // Add this item into the knapsack.
    m_knapsack_table[row][col] = new_value;
    // Update the selection table as we are considering
    // this item.
    m_selection_table[row][col] = 1;
    }
    }
    col++;
    }
    row++;
    }
    return m_knapsack_table[m_item_size][m_knapsack_size];
    }

    void Knapsack::get_items_selected(std::vector<item>& resultItems) {
    int row = m_item_size;
    int col = m_knapsack_size;
    int cap = m_knapsack_size;
    while ( cap > 0 ) {
    if ( m_selection_table[row][col] == 1) {
    resultItems.push_back(m_items[row - 1]);
    cap = cap - m_items[row - 1].capacity;
    col = cap;
    }
    row = row - 1;
    }
    }

    std::ostream &operator << (std::ostream &out, const Knapsack &knp ) {
    out << std::endl;
    out << "SOLUTION MATRIX" << std::endl << std::endl;
    out << std::setw(15) << "Capacity |";
    for ( int i = 0; i <= knp.m_knapsack_size; i++) {
    out << std::setw(5) << i ;
    }
    out << std::endl;
    out << std::endl;

    int row = 0;
    out << std::setw(15) << "NONE |";
    int col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
    out << std::setw(5) << knp.m_knapsack_table[row][col];
    col++;
    }
    out << std::endl;
    row++;
    for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
    itemIterator != knp.m_items.end();
    ++itemIterator) {
    out << "(V:"
    << std::setw(2)
    << itemIterator->value
    << ", "
    << "W:"
    << itemIterator->capacity
    << ")"
    << std::setw(4)
    << "|" ;
    col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
    out << std::setw(5) << knp.m_knapsack_table[row][col];
    col++;
    }
    row++;
    out << std::endl;
    }

    out << std::endl;
    out << "SELECTION MATRIX" << std::endl << std::endl;
    out << std::setw(15) << "Capacity |";
    for ( int i = 0; i <= knp.m_knapsack_size; i++) {
    out << std::setw(5) << i ;
    }
    out << std::endl;
    out << std::endl;

    row = 0;
    out << std::setw(15) << "NONE |";
    col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
    out << std::setw(5) << knp.m_knapsack_table[row][col];
    col++;
    }
    out << std::endl;
    row++;
    for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
    itemIterator != knp.m_items.end();
    ++itemIterator) {
    out << "(V:"
    << std::setw(2)
    << itemIterator->value
    << ", "
    << "W:"
    << itemIterator->capacity
    << ")"
    << std::setw(4)
    << "|" ;
    col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
    out << std::setw(5) << knp.m_selection_table[row][col];
    col++;
    }
    row++;
    out << std::endl;
    }
    return out;
    }

    Knapsack::~Knapsack() {
    }

    int main ( int argc, char **argv) {
    Knapsack knp(18,7);
    knp.add_items(12,4 );
    knp.add_items(10,6 );
    knp.add_items(8 ,5 );
    knp.add_items(11,7 );
    knp.add_items(14,3 );
    knp.add_items(7 ,1 );
    knp.add_items(9 ,6 );
    int solution = knp.solve();
    std::cout << knp;
    std::vector<item> resultItems;
    knp.get_items_selected(resultItems);

    std::cout << "SOLUTION" << std::endl;
    std::cout << '\t' << "Value : " << solution << std::endl;
    std::cout << '\t' << "Items : " << std::endl;
    for ( std::vector<item>::iterator itr = resultItems.begin();
    itr != resultItems.end();
    ++itr) {
    std::cout << '\t' << '\t' << "(V:"
    << std::setw(2)
    << itr->value
    << ", "
    << "W:"
    << itr->capacity
    << ")"
    << std::endl;
    }
    return 0;
    }
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,175
    Rep Power
    2222
    Resubmit as formatted code. It's an unreadable mess. If you can't bother to post readable code, we can't be bothered trying to make sense of that mess. Use code tags to preserve the formatting.

    Disable those stupid smilies! All they do is frak up C++ listings.

    If you seriously think that there's some problem with your code, then tell us what it is! Stop assuming that we are all mind-readers, which we are not!, and don't even begin to think of playing stupid guessing games with us.
  4. #3
  5. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,114
    Rep Power
    1803
    What should it do?
    What does it do?

    How do those two things differ?

    Maybe it runs incorrectly, maybe it does not even compile. Give us a clue here!

    Moreover what have you done to diagnose the issue yourself so far? You have used a debugger right? Most questions posted here could be solved easily if only people used a debugger effectively - the questions would never even get posted. The questions that then got posted would probably be far more interesting too.

    Dumping code and little else and expecting answers is not really credible. With any piece of code that long, there could be any number of issues that we might spot, none of which need be related to your problem of interest.

    And of course no one is going to read that unformatted character pile.
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    I detect the faint whiff (sorry, overpowering stench) of copy/paste coding.

    One quick google later, well, whadaya know...
    nicely formatted code for all to see
    Scroll down to
    Knapsack Problem ( C++ Solution ) June 20, 2011

    Comments on this post

    • ptr2void agrees : Of course! Direct link: https://avdongre.wordpress.com/2011/06/20/knapsack-problem-c-solution/
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    I haz teh codez!
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Dec 2003
    Posts
    2,549
    Rep Power
    2337
    I'm guessing the OP is using something other than the Turbo C++ that the solution provider used, and is running into compilation problems.
    I ♥ ManiacDan & requinix

    This is a sig, and not necessarily a comment on the OP:
    Please don't be a help vampire!
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    Originally Posted by ptr2void
    I'm guessing the OP is using something other than the Turbo C++ that the solution provider used, and is running into compilation problems.
    It seems more likely that the OP is trying to mung the 'found' code so that it will run on TC.
    Code:
    $ diff -B -w original.cpp copied.cpp
    1,4c1,5
    < #include <vector>
    < #include <iostream>
    < #include <iomanip>
    < #include <string>
    ---
    > #include <vector.h>
    > #include <iostream.h>
    > #include <iomanip.h>
    > #include <string.h>
    >
    16c18,19
    <     friend std::ostream &operator <<( std::ostream&, const Knapsack& );
    ---
    >
    > friend std:stream &operator <<( std:stream&, const Knapsack& );
    106c111,112
    < std::ostream &operator << (std::ostream &out, const Knapsack &knp ) {
    ---
    >
    > std:stream &operator << (std:stream &out, const Knapsack &knp ) {
    The obvious thinking that slapping .h on the end of all the includes would fix everything.

    I compiled the original with g++ (ver 3.4.4) and got the same results as the original author. So I guess with a decent modern compiler, it works out of the box.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo