Username *'s Content

C is the best programming language for begginers, it simpe, general purpoused, not interpreted like python and it isn't slow either (like java). BASIC is good too, but nobody uses BASIC anymore...

#79525 Dynamic programming problem

Posted by Username * on 11 September 2014 - 01:57 PM in Coding

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

#79524 About IP addresses

Posted by Username * on 11 September 2014 - 01:54 PM in Coding

They can find out where you live, your OS, ISP and a few other things. It's really not that bad as long as you are using WPA2 and not WEP, because WEP is using a really bad stream cypher. Usually they don't really get your home address because IPs are very inaccurate, for example if I live in Berlin, it will not usually tell you where in Berlin and Berlin is a big city.

#79522 Dynamic programming problem

Posted by Username * on 11 September 2014 - 01:49 PM in Coding

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...