1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <iostream>
#include <array>
#include <string>
#include <fstream>
#include <map>
typedef struct
{
long int value;
long int weight;
} Item;
typedef struct
{
long int index;
long int capacity;
} Couple;
struct CoupleCompare {
bool operator()(const Couple & a, const Couple & b) const noexcept {
return (a.index < b.index) || (a.index == b.index && a.capacity < b.capacity);
}
};
typedef std::array<Item, 2000> Items;
long int compute(long int n, long int w, std::map<Couple, long int>& myMap, Items& items);
Items get_items() {
Items items;
std::string ligne("");
std::ifstream fichier("knapsack_big.txt");
if(fichier){
getline(fichier, ligne);
size_t i(0);
while(getline(fichier, ligne)){
items[i].value = stoi(ligne.substr(0, ligne.find(' ', 0)));
items[i].weight = stoi(ligne.substr(ligne.find(' ', 0), ligne.find(' ', ligne.find(' ', 0) + 1)));
i++;
}
}
else
std::cerr << "Impossible d'ouvrir le fichier" << std::endl;
return items;
}
std::map<Couple, long int, CoupleCompare> initialize(){
std::map<Couple, long int, CoupleCompare> myMap;
for(long int i(0); i < 2000; i++){
Couple c = {0, i};
myMap[c] = 0;
}
return myMap;
}
long int compute(long int n, long int w, Items& items, std::map<Couple, long int, CoupleCompare>& myMap){
Couple c = {n, w};
Couple c2 = {n-1, w};
Couple c3 = {n-1, w-items[n-1].weight};
if(myMap.find(c) != myMap.end())
return myMap.find(c) -> second;
if(myMap.find(c2) != myMap.end() and myMap.find(c3) != myMap.end()) {
myMap[c] = std::max(myMap.find(c2)->second, myMap.find(c3)->second + items[n-1].value);
}
if(w-items[n-1].weight >= 0)
return std::max(compute(n-1, w, items, myMap), compute(n-1, w-items[n-1].weight, items, myMap));
return compute(n-1, w, items, myMap);
}
int main(int argc, char* argv[]){
Items items(get_items());
std::map<Couple, long int, CoupleCompare> myMap(initialize());
std::cout << compute(1999, 2000000, items, myMap);
return 0;
} |
Partager