## Knapsack problem

Moderator: Board moderators

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

### Knapsack problem

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.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
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 Item {
int size, value;
Item *next;

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

friend class Item;
Item *item;
int profit;

public:
this->item = item;
this->profit = profit;
}

}

int printResult () {
cout << "[" << item->value << "," << item->size << "] ";
return item->value;
}
};

if (s < 0) return NULL;
if (next == NULL) {
if (size == s) {
} else return NULL;
}
Answer *p1 = next->profit(s - size);
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;
int S, size, value;

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

fstream fin(argv,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:

http://www-idss.cs.put.poznan.pl/~jaszk ... ngMOKP.htm

Thanks to John Franco for the code We 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
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....

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