#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
struct Item {
int weight;
int value;
};
bool cmp(Item a, Item b) {
double r1 = (double) a.value / a.weight;
double r2 = (double) b.value / b.weight;
return r1 > r2;
}
double fractionalKnapsack(int W, Item arr[], int n) {
sort(arr, arr + n, cmp);
int curWeight = 0;
double finalvalue = 0.0;
for (int i = 0; i < n; i++) {
if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
} else {
int remain = W - curWeight;
finalvalue += arr[i].value * ((double) remain / arr[i].weight);
break;
}
}
return finalvalue;
}
int knapsack(int W, int wt[], int val[], int n) {
vector<vector<int>> K(n + 1, vector<int>(W + 1));
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
int W = 50;
int wt[] = {10, 20, 30};
int val[] = {60, 100, 120};
int n = sizeof(val) / sizeof(val[0]);
clock_t start = clock();
double bestVal = -1;
int maxIter = 1000;
int iter = 0;
while (iter < maxIter && (double) (clock() - start) / CLOCKS_PER_SEC < 1) {
random_shuffle(wt, wt + n);
random_shuffle(val, val + n);
int val1 = knapsack(W, wt, val, n);
double val2 = fractionalKnapsack(W, (Item *) wt, n);
double weightedAvgVal = (0.7 * val1) + (0.3 * val2);
if (weightedAvgVal > bestVal)
bestVal = weightedAvgVal;
iter++;
}
double timeElapsed = (double) (clock() - start) / CLOCKS_PER_SEC;
cout << "Il massimo valore che puo' essere messo nello zaino e': " << bestVal << endl;
cout << "Tempo di esecuzione: " << timeElapsed << " secondi" << endl;
return 0;
}
