fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<climits>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7.  
  8. // Basic structure for the given problem
  9. struct Item {
  10. 	float weight;
  11. 	float volume;
  12.  
  13. 	Item(float weight, float volume) {
  14. 		this->weight = weight;
  15. 		this->volume = volume;
  16. 	}
  17.  
  18. 	bool operator<(const Item &other) const {
  19. 		if(weight == other.weight) {
  20. 			return volume < other.volume;
  21. 		}
  22. 		return weight < other.weight;
  23. 	}
  24. };
  25.  
  26. // Some constant values
  27. const static int INF = INT_MAX / 100;
  28. const static int MAX_NUM_OF_ITEMS = 1000;
  29. const static int MAX_N = 1000;
  30.  
  31. // Parameters that we define in main()
  32. float MAX_VOLUME;
  33. vector<Item> items;
  34.  
  35. // DP lookup tables
  36. int till[MAX_NUM_OF_ITEMS];
  37. float dp[MAX_NUM_OF_ITEMS][MAX_N];
  38.  
  39. /**
  40.  * curIndex: the starting index from where we aim to formulate a new group
  41.  * left: number of groups still left to be formed
  42.  */ 
  43. float solve(int curIndex, int left) {
  44. 	// Baseline condition
  45. 	if(curIndex >= items.size() && left == 0) {
  46. 		return 0;
  47. 	}
  48. 	if(curIndex >= items.size() && left != 0) {
  49. 		return INF;
  50. 	}
  51. 	// If we have no more groups to be found, but there still are items left
  52. 	// then invalidate the solution by returning INF
  53. 	if(left <= 0 && curIndex < items.size()) {
  54. 		return INF;
  55. 	}
  56.  
  57. 	// Our lookup dp table
  58. 	if(dp[curIndex][left] >= 0) {
  59. 		return dp[curIndex][left];
  60. 	}
  61.  
  62. 	// minVal is the metric to optimize which is the `sum of the differences
  63. 	// for each group` we intialize it as INF
  64. 	float minVal = INF;
  65.  
  66. 	// The volume of the items we're going to pick for this group
  67. 	float curVolume = 0;
  68.  
  69. 	// Let's try to see how large can this group be by trying to expand it 
  70. 	// one item at a time
  71. 	for(int i = curIndex; i < items.size(); i++) {
  72. 		// Verfiy we can put the item i in this group or not
  73. 		if(curVolume + items[i].volume > MAX_VOLUME) {
  74. 			break;
  75. 		}
  76. 		curVolume += items[i].volume;
  77. 		// Okay, let's see if it's possible for this group to exist
  78. 		float val = (items[i].weight - items[curIndex].weight) + solve(i + 1, left - 1);
  79. 		if(minVal >= val) {
  80. 			minVal = val;
  81. 			// The lookup table till tells that the group starting at index
  82. 			// curIndex, expands till i, i.e. [curIndex, i] is our valid group
  83. 			till[curIndex] = i + 1;
  84. 		}
  85. 	}
  86. 	// Store the result in dp for memoization and return the value
  87. 	return dp[curIndex][left] = minVal;
  88. }
  89.  
  90. int main() {
  91. 	// The maximum value for Volume
  92. 	MAX_VOLUME = 6;
  93. 	// The number of groups we need
  94. 	int NUM_OF_GROUPS = 5;
  95.  
  96. 	items = vector<Item>({
  97. 	// Item(weight, volume)
  98. 		Item(5, 2),
  99. 		Item(2, 1),
  100. 		Item(10, 3),
  101. 		Item(7, 2),
  102. 		Item(3, 1),
  103. 		Item(5, 3),
  104. 		Item(4, 3),
  105. 		Item(3, 2),
  106. 		Item(10, 1),
  107. 		Item(11, 3),
  108. 		Item(19, 1),
  109. 		Item(21, 2)
  110. 	});
  111.  
  112. 	// Initialize the dp with -1 as default value for unexplored states
  113. 	memset(dp, -1, sizeof dp);
  114.  
  115. 	// Sort the items based on weights first
  116. 	sort(items.begin(), items.end());
  117.  
  118. 	// Solve for the given problem
  119. 	int val = solve(0, NUM_OF_GROUPS);
  120.  
  121. 	// If return value is INF, it means we couldn't distribute it in n
  122. 	// groups due to the contraint on volume or maybe the number of groups
  123. 	// was greater than the number of items we had ^_^
  124. 	if(val >= INF) {
  125. 		cout << "Not possible to distribute in " << NUM_OF_GROUPS;
  126. 		return 0;
  127. 	}
  128.  
  129. 	// If a solution exists, use the lookup till array to find which items
  130. 	// belong to which set	
  131. 	int curIndex = 0, group = 1;
  132. 	while(curIndex < items.size()) {
  133. 		cout << "Group #" << group << ": ";
  134. 		for(int i = curIndex; i < till[curIndex]; i++)
  135. 			cout << "(" << items[i].weight << ", " << items[i].volume << ") ";
  136. 		cout << '\n';
  137. 		group++;	
  138. 		curIndex = till[curIndex];
  139. 	}
  140. }
  141.  
Success #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Group #1: (2, 1) (3, 1) (3, 2) 
Group #2: (4, 3) (5, 2) 
Group #3: (5, 3) (7, 2) (10, 1) 
Group #4: (10, 3) (11, 3) 
Group #5: (19, 1) (21, 2)
https://ideone.com/pkfyxg
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!