1) City Budget Allocation
Algorithm:
0/1 Knapsack (Dynamic Programming)
Problem:
Optimize city project selection under limited budget to maximize impact.
Solution:
Use 0/1 Knapsack DP to select projects efficiently within the budget constraint.
SDGs:
SDG1: No Poverty
SDG8: Decent Work & Economic Growth
SDG11: Sustainable Cities
C++ Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for(int i=0;i<n;i++) cin >> w[i] >> v[i];
vector<long long> dp(W+1,0);
for(int i=0;i<n;i++) {
for(int cap=W; cap>=w[i]; --cap)
dp[cap] = max(dp[cap], dp[cap-w[i]] + v[i]);
}
cout << *max_element(dp.begin(), dp.end());
}
2) Tax Officer Route Optimization
Algorithm:
Dijkstra / Floyd-Warshall
Problem:
Compute shortest inspection routes across city zones for tax officers.
Solution:
Use Dijkstra (or Floyd-Warshall for all pairs) to find shortest paths for route optimization.
SDGs:
SDG9: Industry & Infrastructure
SDG11: Sustainable Cities
SDG16: Peace & Justice
C++ Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> g(n);
for(int i=0;i<m;i++) {
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
int s; cin >> s;
const long long INF = 1e18;
vector<long long> d(n, INF);
d[s] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>> pq;
pq.push({0, s});
while(!pq.empty()) {
auto [du,u] = pq.top(); pq.pop();
if(du != d[u]) continue;
for(auto [v,w] : g[u])
if(d[v] > du + w) {
d[v] = du + w;
pq.push({d[v], v});
}
}
for(int i=0;i<n;i++) cout << d[i] << " ";
}
3) Smart Parking Fee Prediction
Algorithm:
Segment Tree + Lookup Table
Problem:
Predict optimal parking fees based on usage trends.
Solution:
Use Segment Tree to compute demand in ranges and Lookup Table to assign fees.
SDGs:
SDG9: Industry & Infrastructure
SDG11: Sustainable Cities
SDG13: Climate Action
C++ Code:
#include <bits/stdc++.h>
using namespace std;
struct Seg {
int n;
vector<long long> st;
Seg(int n):n(n),st(4*n,0){}
void build(vector<int>&a,int p,int l,int r){
if(l==r){ st[p]=a[l]; return;}
int m=(l+r)/2;
build(a,2*p,l,m); build(a,2*p+1,m+1,r);
st[p]=st[2*p]+st[2*p+1];
}
long long qry(int p,int l,int r,int ql,int qr){
if(qr<l||r<ql) return 0;
if(ql<=l && r<=qr) return st[p];
int m=(l+r)/2;
return qry(2*p,l,m,ql,qr)+qry(2*p+1,m+1,r,ql,qr);
}
};
int main(){
int n; cin>>n; vector<int>a(n); for(int i=0;i<n;i++) cin>>a[i];
Seg seg(n); seg.build(a,1,0,n-1);
int q; cin>>q;
auto fee=[&](long long demand){
if(demand<=100) return 10;
if(demand<=500) return 20;
if(demand<=1000) return 30;
return 50;
};
while(q--){
int l,r; cin>>l>>r;
long long d = seg.qry(1,0,n-1,l,r);
cout<<fee(d)<<"\n";
}
}
4) Public Transport Scheduling
Algorithm:
Greedy Algorithm / Interval Scheduling
Problem:
Schedule buses to maximize coverage without overlapping routes and reduce congestion.
Solution:
Sort routes by end time and use greedy selection to assign buses to the maximum number of non-overlapping routes.
SDGs:
SDG9: Industry & Infrastructure
SDG11: Sustainable Cities
C++ Code:
#include <bits/stdc++.h>
using namespace std;
struct Bus { int start, end; };
int main() {
int n; cin >> n;
vector<Bus> buses(n);
for(int i=0;i<n;i++) cin >> buses[i].start >> buses[i].end;
sort(buses.begin(), buses.end(), [](Bus a, Bus b){ return a.end < b.end; });
int count=0, lastEnd=0;
for(auto b : buses){
if(b.start >= lastEnd){
count++; lastEnd=b.end;
}
}
cout << count;
}
5) Waste Management Optimization
Algorithm:
Minimum Spanning Tree (Prim / Kruskal)
Problem:
Connect city waste collection points minimizing transportation cost.
Solution:
Use MST to connect all collection points with minimal total distance/cost.
SDGs:
SDG6: Clean Water & Sanitation
SDG11: Sustainable Cities
SDG12: Responsible Consumption
C++ Code:
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u,v,w; };
int find(vector<int>& parent,int x){ return parent[x]==x?x:parent[x]=find(parent,parent[x]); }
int main(){
int n,m; cin>>n>>m;
vector<Edge> edges(m);
for(int i=0;i<m;i++) cin>>edges[i].u>>edges[i].v>>edges[i].w;
sort(edges.begin(), edges.end(), [](Edge a,Edge b){ return a.w<b.w; });
vector<int> parent(n); iota(parent.begin(), parent.end(),0);
int cost=0;
for(auto e : edges){
int pu=find(parent,e.u), pv=find(parent,e.v);
if(pu!=pv){ parent[pu]=pv; cost+=e.w; }
}
cout<<cost;
}
6) Water Supply Network Design
Algorithm:
Floyd-Warshall / Shortest Path
Problem:
Ensure optimal water distribution between all neighborhoods.
Solution:
Compute all-pairs shortest paths to optimize pipeline routing and reduce losses.
SDGs:
SDG6: Clean Water & Sanitation
SDG11: Sustainable Cities
SDG13: Climate Action
C++ Code:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
vector<vector<int>> dist(n, vector<int>(n,1e9));
for(int i=0;i<n;i++) dist[i][i]=0;
int m; cin>>m;
for(int i=0;i<m;i++){
int u,v,w; cin>>u>>v>>w;
dist[u][v]=w; dist[v][u]=w;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
for(int i=0;i<n;i++){ for(int j=0;j<n;j++) cout<<dist[i][j]<<" "; cout<<endl; }
}
7) Electric Grid Load Balancing
Algorithm:
Max Flow (Edmonds-Karp)
Problem:
Distribute electricity to all city sectors without overloading lines.
Solution:
Use Max Flow to model capacity of power lines and ensure balanced distribution.
SDGs:
SDG7: Affordable Clean Energy
SDG9: Industry & Infrastructure
C++ Code:
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
int n,m; cin>>n>>m;
vector<vector<int>> capacity(n, vector<int>(n,0));
for(int i=0;i<m;i++){
int u,v,c; cin>>u>>v>>c;
capacity[u][v]=c;
}
int s,t; cin>>s>>t;
int flow=0;
while(true){
vector<int> parent(n,-1);
queue<int> q; q.push(s);
parent[s]=-2;
while(!q.empty() && parent[t]==-1){
int u=q.front(); q.pop();
for(int v=0;v<n;v++)
if(parent[v]==-1 && capacity[u][v]>0){ parent[v]=u; q.push(v); }
}
if(parent[t]==-1) break;
int cur=t, f=INF;
while(cur!=s){ f=min(f, capacity[parent[cur]][cur]); cur=parent[cur]; }
cur=t;
while(cur!=s){ capacity[parent[cur]][cur]-=f; capacity[cur][parent[cur]]+=f; cur=parent[cur]; }
flow+=f;
}
cout<<flow;
}
8) Emergency Response Route Planning
Algorithm:
A* / Dijkstra Algorithm
Problem:
Plan fastest emergency vehicle routes during city crises.
Solution:
Use shortest-path algorithm (A* or Dijkstra) for optimal routing under constraints.
SDGs:
SDG3: Good Health & Well-being
SDG11: Sustainable Cities
C++ Code:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m; cin>>n>>m;
vector<vector<pair<int,int>>> g(n);
for(int i=0;i<m;i++){
int u,v,w; cin>>u>>v>>w;
g[u].push_back({v,w}); g[v].push_back({u,w});
}
int s; cin>>s;
vector<long long> d(n,1e18); d[s]=0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
pq.push({0,s});
while(!pq.empty()){
auto [du,u]=pq.top(); pq.pop();
if(du!=d[u]) continue;
for(auto [v,w]: g[u]) if(d[v]>du+w){ d[v]=du+w; pq.push({d[v],v}); }
}
for(int i=0;i<n;i++) cout<<d[i]<<" ";
}
9) Traffic Light Scheduling
Algorithm:
Graph Coloring / Greedy
Problem:
Schedule traffic lights to reduce congestion at intersections.
Solution:
Model intersections as a graph, color nodes (green cycles) using greedy approach to avoid conflicts.
SDGs:
SDG11: Sustainable Cities
SDG13: Climate Action
C++ Code:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m; cin>>n>>m;
vector<vector<int>> g(n);
for(int i=0;i<m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }
vector<int> color(n,-1);
for(int u=0;u<n;u++){
vector<bool> used(n,false);
for(auto v:g[u]) if(color[v]!=-1) used[color[v]]=true;
for(int c=0;c<n;c++) if(!used[c]){ color[u]=c; break; }
}
for(int i=0;i<n;i++) cout<<color[i]<<" ";
}
10) Renewable Energy Placement
Algorithm:
Greedy / Knapsack
Problem:
Place solar panels/wind turbines to maximize energy output under cost constraints.
Solution:
Use greedy selection based on output/cost ratio to select locations efficiently.
SDGs:
SDG7: Affordable Clean Energy
SDG11: Sustainable Cities
SDG13: Climate Action
C++ Code:
#include <bits/stdc++.h>
using namespace std;
struct Site{ int cost, output; };
int main(){
int n,budget; cin>>n>>budget;
vector<Site> sites(n);
for(int i=0;i<n;i++) cin>>sites[i].cost>>sites[i].output;
sort(sites.begin(), sites.end(), [](Site a,Site b){ return (double)a.output/a.cost > (double)b.output/b.cost; });
int total=0;
for(auto s:sites){
if(s.cost<=budget){ budget-=s.cost; total+=s.output; }
}
cout<<total;
}