Jump to content

Photo

Dynamic programming problem


  • Please log in to reply
14 replies to this topic

#1 Username *

Username *

    Byte

  • Members
  • 16 posts

Posted 11 September 2014 - 07:49 AM

So... I have a code that's not working for the 1-0 knapsack problem (it's supposed to give me the greatest value you can get, not the items themselves), please find it.

 

/*
problem description:
you have a knapsack with a maximum capacity kw and a number of objects objs with a value and weight. If you put and object in the knapsack it's already in the knapsack and you can't add the object again in it. What is the highest added value of the objects you can get while the added weight of the objects is not greater than the maximum capacity.
*/
#include <iostream>
using namespace std;

struct obj{
    int value;
    int weight;
}; //object struct describing the object with a value and a weight

int main(void){
    int i,j,kw,objs,val,left;
    cout<<"knapsack max weight: ";
    cin>>kw;
    cout<<"number of objects: ";
    cin>>objs;
    obj object[objs];
    for(i=1;i<=objs;i++){
        cout<<"object "<<i<<":"<<endl;
        cout<<"value: ";
        cin>>object[i].value;
        cout<<"weight: ";
        cin>>object[i].weight;
        cout<<endl;
    }
    //Until here I just initiated variables and wrote down the reading functions stuff
    int matrix[kw][objs]; //This matrix should contain the all the knapsack problems with the max capacity smaller and equal to kw and the number of objects smaller or equal to objs
    bool keep[kw][objs]; //You shouldn't care about this matrix
    for(i=0;i<=objs;i++)
        matrix[0][i]=0;
    for(i=0;i<=kw;i++)
        matrix[i][0]=0;
    //In dynamic programming you need a base case so i setted all the knapsack cases with kw=0 and the number of objs=0 to zero
    for(i=1;i<=objs;i++){
        for(j=1;j<=kw;j++){
            if(object[j].weight>i){ //If the object is heavier, the obvious solution is the knapsack problem with less objects
                keep[i][j]=0;
                matrix[i][j]=matrix[i-1][j];
            }
            else{
                left=kw-object[i].weight;
                val=object[i].weight+matrix[i-1][left]; //Once you put an object in you have left space left and i-1 objects left, this is another knapsack problem, so you add its result and get the optimal matrix[i][j] value
                if(val>matrix[i-1][j]){ //If the solution is better than the one with fewer objects, use that solution instead
                    keep[i][j]=1;
                    matrix[i][j]=val;
                }
                else{ //If not, use the i objects solution instead
                    keep[i][j]=0;
                    matrix[i][j]=matrix[i-1][j];
                }
            }
        }
    }
    cout<<"RESULT: "<<matrix[objs][kw]<<endl; //outputs the result
    return 0;
}

Yes, I am a begginer in computer science, the excuse is that I'm in middle school...


Religious+fanaticism_e9d588_4123667.png


#2 Guest_ElatedOwl_*

Guest_ElatedOwl_*
  • Guests

Posted 11 September 2014 - 07:51 AM

Can you explain your problem a little more in depth?

  1. Is it compiling?
  2. What exactly is it supposed to do?
  3. What is it doing incorrectly?


#3 Username *

Username *

    Byte

  • Members
  • 16 posts

Posted 11 September 2014 - 07:57 AM

Of course it's not a compiling problem, it's a logical problem (a bug). It outputs a wrong answer. I said it's a 1-0 knapsack problem and specified what it's supposed to do. If you don't know what the knapsack problem is watch this video: http://www.youtube.c...h?v=EH6h7WA7sDw


Religious+fanaticism_e9d588_4123667.png


#4 Guest_ElatedOwl_*

Guest_ElatedOwl_*
  • Guests

Posted 11 September 2014 - 08:15 AM

Logical problems and syntax problems are both bugs. Whenever you ask for programming help you need to explain your situation as if you're talking to a rubber duck - you can't be ambigious and you need to explain every relevant detail. Yeah, you said it's a 1-0 knapsack problem, but that means absolutely nothing to almost anyone.



#5 Username *

Username *

    Byte

  • Members
  • 16 posts

Posted 11 September 2014 - 08:20 AM

Sorry for the bug thing, in my school they teached us something else. I don't really expect help from a rubber duck.


Religious+fanaticism_e9d588_4123667.png


#6 fae

fae

    Terabyte

  • Members
  • 1,307 posts
  • LocationOver the hills, where the seven dwarfs dwell

Posted 11 September 2014 - 08:33 AM

comments would be helpful..


Et j'aime la nuit écouter les étoiles. C'est comme cinq cent millions de grelots. - Antoine de Saint-Exupéry


#7 SushiKitten

SushiKitten

    Coffee Cat

  • Members
  • 1,916 posts
  • LocationCanada

Posted 11 September 2014 - 09:22 AM

I don't know how many times I've consulted in a friend or started an email to send to my prof and realized my problem on my own while trying to explain my situation, so rubber duck decoding can work. Like emo said, saying its a 1-0 knapsack problem means nothing to us.

With that in mind, what's the program supposed to do and hpw are you going about it?

#8 Username *

Username *

    Byte

  • Members
  • 16 posts

Posted 11 September 2014 - 09:29 AM

I posted a link with a video about the problem.


Religious+fanaticism_e9d588_4123667.png


#9 Guest_ElatedOwl_*

Guest_ElatedOwl_*
  • Guests

Posted 11 September 2014 - 09:38 AM

I posted a link with a video about the problem.

I hope you don't think I'm trying to come across as rude but the video isn't really going to help us.

 

We need to know exactly what you're doing, why you're doing it, what you expect to happen versus what is actually happening. If you can't provide that we can't really help you.

 

If you can't answer those questions then ultimately you need to go back through what steps you think you need to solve the problem.



#10 fae

fae

    Terabyte

  • Members
  • 1,307 posts
  • LocationOver the hills, where the seven dwarfs dwell

Posted 11 September 2014 - 09:42 AM

that's why i said comments.. I learned to put a comment for each line of code.


Et j'aime la nuit écouter les étoiles. C'est comme cinq cent millions de grelots. - Antoine de Saint-Exupéry


#11 SushiKitten

SushiKitten

    Coffee Cat

  • Members
  • 1,916 posts
  • LocationCanada

Posted 11 September 2014 - 09:52 AM

We aren't going to sit down, try to learn the problem you're trying to solve through a YT video, decipher commentless code to figure out what you're trying to do and give you an answer. I'm all for working together and helping you, but I'm not putting that much effort in for a stranger, no offense.

Think about what your solution for the problem is supposed to do step by step and look at your code and ask yourself a) is your solution valid? And b ) does your code follow your solution? That's why we're trying to get you to discuss this with us, we'll get to an answer faster.

#12 Username *

Username *

    Byte

  • Members
  • 16 posts

Posted 11 September 2014 - 12:26 PM

Ok, I'll add some comments.


Religious+fanaticism_e9d588_4123667.png


#13 fae

fae

    Terabyte

  • Members
  • 1,307 posts
  • LocationOver the hills, where the seven dwarfs dwell

Posted 11 September 2014 - 01:31 PM

Ok so I haven't programmed in C in quite some time, but I'm pretty sure that this:

for(i=0;i<=objs;i++)
   matrix[0][i]=0;
for(i=0;i<=kw;i++)
   matrix[i][0]=0;

only zeros the first line and the first column..

 

also here

 

for(i=1;i<=objs;i++){
    for(j=1;j<=kw;j++){

isn't this out of range.. you should start a i=0

 

and what is this comparison for?

if(object[j].weight>i){

 


Et j'aime la nuit écouter les étoiles. C'est comme cinq cent millions de grelots. - Antoine de Saint-Exupéry


#14 Guest_ElatedOwl_*

Guest_ElatedOwl_*
  • Guests

Posted 11 September 2014 - 01:37 PM

Ok so I haven't programmed in C in quite some time, but I'm pretty sure that this:

for(i=0;i<=objs;i++)
   matrix[0][i]=0;
for(i=0;i<=kw;i++)
   matrix[i][0]=0;

only zeros the first line and the first column..

 

also here

 

for(i=1;i<=objs;i++){
    for(j=1;j<=kw;j++){

isn't this out of range.. you should start a i=0

 

and what is this comparison for?

if(object[j].weight>i){

I was thrown off by it too at first, but the approach he's trying to implement does it intentionally. (it will scale significantly better with this manner)

 

http://cse.unl.edu/~...Programming.pdf Page 4 visualizes the matrix and shows the pseudo code.
 
Basically the idea instead of trying every possible combination is to find the max value at any given weight, each row of the matrix specifying the item so the last column of the last row should the be the maximum value you can carry.


#15 Guest_ElatedOwl_*

Guest_ElatedOwl_*
  • Guests

Posted 11 September 2014 - 02:02 PM

Here's the working solution.

 

Your code here

            else{
                left=kw-object[i].weight;
                val=object[i].weight+matrix[i-1][left]; //Once you put an object in you have left space left and i-1 objects left, this is another knapsack problem, so you add its result and get the optimal matrix[i][j] value
                if(val>matrix[i-1][j]){ //If the solution is better than the one with fewer objects, use that solution instead
                    keep[i][j]=1;
                    matrix[i][j]=val;
                }
                else{ //If not, use the i objects solution instead
                    keep[i][j]=0;
                    matrix[i][j]=matrix[i-1][j];
                }
            } 

 

was the issue. Specifically,

 

val=object[i].weight+matrix[i-1][left];

 

should be

 

val=object[i].value+matrix[i-1][left];