A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d0/d61/knapsack_8cpp_source.html below:

TheAlgorithms/C++: greedy_algorithms/knapsack.cpp Source File

9float

profitPerUnit(

Item

x) {

return

(

float

)x.profit / (float)x.weight; }

11int

partition(

Item

arr[],

int

low,

int

high) {

12 Item

pivot = arr[high];

15 for

(

int

j = low; j < high; j++) {

18 if

(profitPerUnit(arr[j]) <= profitPerUnit(pivot)) {

25 Item

temp = arr[i + 1];

26

arr[i + 1] = arr[high];

31void

quickSort(

Item

arr[],

int

low,

int

high) {

33 int

p = partition(arr, low, high);

35

quickSort(arr, low, p - 1);

36

quickSort(arr, p + 1, high);

41

cout <<

"\nEnter the capacity of the knapsack : "

;

44

cout <<

"\n Enter the number of Items : "

;

48 for

(

int

i = 0; i < n; i++) {

49

cout <<

"\nEnter the weight and profit of item "

<< i + 1 <<

" : "

;

50

cin >> itemArray[i].weight;

51

cin >> itemArray[i].profit;

54

quickSort(itemArray, 0, n - 1);

60 while

(capacity > 0 && --i >= 0) {

61 if

(capacity >= itemArray[i].weight) {

62

maxProfit += itemArray[i].profit;

63

capacity -= itemArray[i].weight;

64

cout <<

"\n\t"

<< itemArray[i].weight <<

"\t" 65

<< itemArray[i].profit;

67

maxProfit += profitPerUnit(itemArray[i]) * capacity;

68

cout <<

"\n\t"

<< capacity <<

"\t" 69

<< profitPerUnit(itemArray[i]) * capacity;

75

cout <<

"\nMax Profit : "

<< maxProfit;

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4