Knapsack problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

Knapsack problem

Post by Pupirev Sergei » Mon Mar 17, 2003 7:13 pm

Please, help me to solve this problem:
You are giving n (n<=50) knapsacks and R(R<=1023) items each of size ri (ri<=128). You should determine the maximum number of items, which can be put to the knapsacks.
Thanks.

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Mon Mar 17, 2003 8:39 pm

Knapsack Problem:

Given: A collection of items, each with a value and a size. A "knapsack" of specified size, say S.

Find: A subset of items whose sizes sum to S (that is, precidely fill the knapsack) and whose sum of values is greatest among all subsets filling the knapsack.

In the solution below data is input via file with first line specifying S and each remaining line specifying the size and value of each item.

[cpp]
#include < fstream.h >
#include < iostream.h >
#include < stdlib.h >

class Answer;

class Item {
friend class Answer;
int size, value;
Item *next;

public:
Item (int size, int value, Item *next) {
this->size = size;
this->value = value;
this->next = next;
}
Answer *profit (int s);
};

class Answer {
friend class Item;
Item *item;
int profit;
Answer *answer;

public:
Answer (Item *item, int profit, Answer *answer) {
this->item = item;
this->profit = profit;
if (answer != NULL) this->profit += answer->profit;
this->answer = answer;
}

~Answer() {
if (answer != NULL) delete answer;
}

int printResult () {
cout << "[" << item->value << "," << item->size << "] ";
if (answer != NULL) return item->value + answer->printResult();
return item->value;
}
};

Answer *Item::profit (int s) {
if (s < 0) return NULL;
if (next == NULL) {
if (size == s) {
return new Answer(this, value, NULL);
} else return NULL;
}
Answer *p1 = next->profit(s - size);
Answer *p2 = next->profit(s);
if (p1 == NULL) return p2;
if (p2 == NULL) return new Answer(this, value, p1);
if (p1->profit+value < p2->profit) { delete p1; return p2; }
else { delete p2; return new Answer(this, value, p1); }
}

void main (int argc, char **argv) {
Item *items = NULL;
Answer *result;
int S, size, value;

if (argc != 2) {
cout << "Usage: " << argv[0] << " \n";
exit (0);
}

fstream fin(argv[1],ios::in);
fin >> S;
while (fin >> size >> value) items = new Item(size, value, items);
fin.close();

if ((result = items->profit(S)) == NULL) {
cout << "No Solution\n";
exit(0);
}
cout << "\nProfit: " << result->printResult() << "\n";
}


[/cpp]

You can also go:

A very very good link:
http://www-idss.cs.put.poznan.pl/~jaszk ... ngMOKP.htm

Thanks to John Franco for the code
ImageWe are all in a circular way, no advances, only moving and moving!

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

Post by Pupirev Sergei » Tue Mar 18, 2003 3:12 pm

Thanks for your link Moni!
But my problem is easier, i think. You see, all the weights of items are one, and the main difficulty is that there are many knapsacks (<=50). If you have any ideas can you help?

arabiukas
New poster
Posts: 2
Joined: Fri Mar 21, 2003 11:03 am

I have this problem now....

Post by arabiukas » Sat Mar 22, 2003 12:38 pm

Do you know now how to solve it.....

you talk about usaco problem(fence rails)?

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Thu Oct 09, 2003 6:41 am

I want to know how multiple knapsack (0/1) problems can be solved.

Post Reply

Return to “Algorithms”