using namespace std;↵
↵
int main() {↵
int n;↵
cout << "Enter number of coin denominations: ";↵
cin >> n;↵
↵
vector<int> coins(n);↵
cout << "Enter the coin denominations: ";↵
for (int i = 0; i < n; i++) cin >> coins[i];↵
↵
int amount;↵
cout << "Enter the target amount: ";↵
cin >> amount;↵
↵
// Sort coins in descending order for greedy selection↵
sort(coins.rbegin(), coins.rend());↵
↵
vector<int> result;↵
int remaining = amount;↵
↵
for (int i = 0; i < n && remaining > 0; i++) {↵
while (coins[i] <= remaining) {↵
remaining -= coins[i];↵
result.push_back(coins[i]);↵
}↵
}↵
↵
if (remaining != 0) {↵
cout << "Greedy approach could not form the exact amount ";↵
cout << "(this coin system may not be canonical).\n";↵
} else {↵
cout << "Number of coins used: " << result.size() << "\n";↵
cout << "Coins used: ";↵
for (int c : result) cout << c << " ";↵
cout << "\n";↵
}↵
↵
return 0;↵
}
↵
## 1. Coin Changing (Dynamic Programming)↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int n;↵
cout << "Enter number of coin denominations: ";↵
cin >> n;↵
↵
vector<int> coins(n);↵
cout << "Enter the coin denominations: ";↵
for (int i = 0; i < n; i++) cin >> coins[i];↵
↵
int amount;↵
cout << "Enter the target amount: ";↵
cin >> amount;↵
↵
vector<int> dp(amount + 1, INT_MAX);↵
vector<int> lastCoin(amount + 1, -1);↵
dp[0] = 0;↵
↵
for (int i = 1; i <= amount; i++) {↵
for (int j = 0; j < n; j++) {↵
if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {↵
if (dp[i - coins[j]] + 1 < dp[i]) {↵
dp[i] = dp[i - coins[j]] + 1;↵
lastCoin[i] = coins[j];↵
}↵
}↵
}↵
}↵
↵
if (dp[amount] == INT_MAX) {↵
cout << "It is not possible to form the amount with given coins.\n";↵
} else {↵
cout << "Minimum number of coins required: " << dp[amount] << "\n";↵
// Reconstruct the coins used↵
vector<int> used;↵
int cur = amount;↵
while (cur > 0) {↵
used.push_back(lastCoin[cur]);↵
cur -= lastCoin[cur];↵
}↵
cout << "Coins used: ";↵
for (int c : used) cout << c << " ";↵
cout << "\n";↵
}↵
↵
return 0;↵
}↵
```↵
↵
## 2. Coin Changing (Greedy Approach)↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int n;↵
cout << "Enter number of coin denominations: ";↵
cin >> n;↵
↵
vector<int> coins(n);↵
cout << "Enter the coin denominations: ";↵
for (int i = 0; i < n; i++) cin >> coins[i];↵
↵
int amount;↵
cout << "Enter the target amount: ";↵
cin >> amount;↵
↵
// Sort coins in descending order for greedy selection↵
sort(coins.rbegin(), coins.rend());↵
↵
vector<int> result;↵
int remaining = amount;↵
↵
for (int i = 0; i < n && remaining > 0; i++) {↵
while (coins[i] <= remaining) {↵
remaining -= coins[i];↵
result.push_back(coins[i]);↵
}↵
}↵
↵
if (remaining != 0) {↵
cout << "Greedy approach could not form the exact amount ";↵
cout << "(this coin system may not be canonical).\n";↵
} else {↵
cout << "Number of coins used: " << result.size() << "\n";↵
cout << "Coins used: ";↵
for (int c : result) cout << c << " ";↵
cout << "\n";↵
}↵
↵
return 0;↵
}↵
```↵
↵
## 3. Fractional Knapsack (Greedy Approach)↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct Item {↵
double weight;↵
double value;↵
double ratio;↵
};↵
↵
int main() {↵
int n;↵
cout << "Enter number of items: ";↵
cin >> n;↵
↵
vector<Item> items(n);↵
for (int i = 0; i < n; i++) {↵
cout << "Enter weight and value of item " << i + 1 << ": ";↵
cin >> items[i].weight >> items[i].value;↵
items[i].ratio = items[i].value / items[i].weight;↵
}↵
↵
double capacity;↵
cout << "Enter the knapsack capacity: ";↵
cin >> capacity;↵
↵
// Sort items by value/weight ratio in descending order↵
sort(items.begin(), items.end(), [](const Item &a, const Item &b) {↵
return a.ratio > b.ratio;↵
});↵
↵
double totalValue = 0.0;↵
double remainingCapacity = capacity;↵
↵
cout << "\nItems selected (fraction taken):\n";↵
for (int i = 0; i < n && remainingCapacity > 0; i++) {↵
if (items[i].weight <= remainingCapacity) {↵
// Take the whole item↵
remainingCapacity -= items[i].weight;↵
totalValue += items[i].value;↵
cout << "Item (w=" << items[i].weight << ", v=" << items[i].value↵
<< ") -> Taken fully (100%)\n";↵
} else {↵
// Take fraction of the item↵
double fraction = remainingCapacity / items[i].weight;↵
totalValue += items[i].value * fraction;↵
cout << "Item (w=" << items[i].weight << ", v=" << items[i].value↵
<< ") -> Taken " << fraction * 100 << "%\n";↵
remainingCapacity = 0;↵
}↵
}↵
↵
cout << fixed << setprecision(2);↵
cout << "\nMaximum value obtainable: " << totalValue << "\n";↵
↵
return 0;↵
}↵
```↵
↵
## 4. Bin Packing (First Fit Approach)↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int n;↵
cout << "Enter number of items: ";↵
cin >> n;↵
↵
vector<int> items(n);↵
cout << "Enter sizes of the items: ";↵
for (int i = 0; i < n; i++) cin >> items[i];↵
↵
int binCapacity;↵
cout << "Enter bin capacity: ";↵
cin >> binCapacity;↵
↵
vector<int> binRemaining; // remaining space in each used bin↵
vector<vector<int>> binContents;↵
↵
for (int i = 0; i < n; i++) {↵
bool placed = false;↵
↵
// Try to place item in the first bin that has enough space↵
for (int j = 0; j < (int)binRemaining.size(); j++) {↵
if (binRemaining[j] >= items[i]) {↵
binRemaining[j] -= items[i];↵
binContents[j].push_back(items[i]);↵
placed = true;↵
break;↵
}↵
}↵
↵
// If it doesn't fit in any existing bin, open a new bin↵
if (!placed) {↵
binRemaining.push_back(binCapacity - items[i]);↵
binContents.push_back({items[i]});↵
}↵
}↵
↵
cout << "\nTotal bins used: " << binContents.size() << "\n";↵
for (int j = 0; j < (int)binContents.size(); j++) {↵
cout << "Bin " << j + 1 << ": ";↵
int sum = 0;↵
for (int item : binContents[j]) {↵
cout << item << " ";↵
sum += item;↵
}↵
cout << "(used " << sum << "/" << binCapacity << ")\n";↵
}↵
↵
return 0;↵
}↵
```↵
↵
### Notes↵
- **Coin Changing (DP)** always finds the optimal (minimum) number of coins, even for non-canonical coin systems.↵
- **Coin Changing (Greedy)** is faster but can fail on non-standard denominations (e.g., coins `{1, 3, 4}` for amount `6`).↵
- **Fractional Knapsack** sorts by value/weight ratio and allows partial items, so greedy is provably optimal here.↵
- **Bin Packing** uses the **First Fit** heuristic — simple and reasonably good, but not always optimal (bin packing is NP-hard in general).
