0-1 Capital Investment Selection Problem

Solving with Python

What is the 0-1 Capital Investment Selection Problem?

The 0-1 Capital Investment Selection Problem is a classic combinatorial optimization problem where a company must decide which investment projects to undertake given a limited budget. Each project is either selected (1) or not selected (0) — you can’t partially invest.

This is a variant of the 0-1 Knapsack Problem, and can be formulated as:

$$\max \sum_{i=1}^{n} v_i x_i$$

Subject to:

$$\sum_{i=1}^{n} c_i x_i \leq B$$

$$x_i \in {0, 1}, \quad i = 1, 2, \ldots, n$$

Where:

  • $v_i$ = expected NPV (Net Present Value) of project $i$
  • $c_i$ = required investment cost of project $i$
  • $B$ = total available budget
  • $x_i$ = binary decision variable (1 = invest, 0 = skip)

Concrete Example

A company has a budget of ¥500 million and is evaluating 10 candidate projects:

Project Cost (¥M) Expected NPV (¥M)
P1 120 150
P2 80 100
P3 200 230
P4 150 160
P5 60 90
P6 170 200
P7 90 110
P8 50 70
P9 130 140
P10 40 65

Goal: Maximize total NPV within the ¥500M budget.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# ============================================================
# 0-1 Capital Investment Selection Problem
# Solver: Dynamic Programming + Visualization
# ============================================================

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from mpl_toolkits.mplot3d import Axes3D
import itertools

# ── 1. Problem Data ──────────────────────────────────────────
projects = {
    'name' : ['P1','P2','P3','P4','P5','P6','P7','P8','P9','P10'],
    'cost' : [120, 80, 200, 150, 60, 170, 90, 50, 130, 40],
    'npv'  : [150, 100, 230, 160, 90, 200, 110, 70, 140, 65],
}

n       = len(projects['name'])
costs   = np.array(projects['cost'])
npvs    = np.array(projects['npv'])
names   = projects['name']
BUDGET  = 500   # ¥ million

# ── 2. Dynamic Programming Solver ────────────────────────────
def solve_01knapsack(costs, npvs, budget):
    """Standard DP for 0-1 knapsack. Returns dp table and selection."""
    n = len(costs)
    # dp[i][w] = max NPV using first i items with budget w
    dp = np.zeros((n + 1, budget + 1), dtype=np.int64)

    for i in range(1, n + 1):
        c = costs[i - 1]
        v = npvs[i - 1]
        for w in range(budget + 1):
            if c <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - c] + v)
            else:
                dp[i][w] = dp[i-1][w]

    # Back-tracking to find selected projects
    selected = []
    w = budget
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i - 1)   # 0-indexed
            w -= costs[i - 1]
    selected.reverse()
    return dp, selected

dp_table, selected_idx = solve_01knapsack(costs, npvs, BUDGET)

# ── 3. Results Summary ────────────────────────────────────────
total_cost = sum(costs[i] for i in selected_idx)
total_npv  = sum(npvs[i]  for i in selected_idx)
selected_names = [names[i] for i in selected_idx]

print("=" * 45)
print("  0-1 Capital Investment Selection Result")
print("=" * 45)
print(f"  Budget           : ¥{BUDGET} M")
print(f"  Selected Projects: {selected_names}")
print(f"  Total Cost       : ¥{total_cost} M")
print(f"  Total NPV        : ¥{total_npv} M")
print(f"  Remaining Budget : ¥{BUDGET - total_cost} M")
print("=" * 45)

# ── 4. Profitability Index (ROI per ¥1M) ─────────────────────
pi = npvs / costs   # Profitability Index

# ── 5. Visualization ─────────────────────────────────────────
fig = plt.figure(figsize=(18, 14))
fig.suptitle("0-1 Capital Investment Selection Problem", fontsize=16, fontweight='bold', y=0.98)

colors_all = ['#2ecc71' if i in selected_idx else '#e74c3c' for i in range(n)]

# ── 5-1. Cost vs NPV Scatter ──────────────────────────────────
ax1 = fig.add_subplot(2, 3, 1)
for i in range(n):
    ax1.scatter(costs[i], npvs[i], color=colors_all[i], s=120, zorder=5)
    ax1.annotate(names[i], (costs[i], npvs[i]),
                 textcoords="offset points", xytext=(5, 5), fontsize=9)
ax1.set_xlabel("Investment Cost (¥M)")
ax1.set_ylabel("Expected NPV (¥M)")
ax1.set_title("Cost vs Expected NPV")
green_patch = mpatches.Patch(color='#2ecc71', label='Selected')
red_patch   = mpatches.Patch(color='#e74c3c', label='Not Selected')
ax1.legend(handles=[green_patch, red_patch])
ax1.grid(True, alpha=0.3)

# ── 5-2. Profitability Index Bar Chart ───────────────────────
ax2 = fig.add_subplot(2, 3, 2)
bars = ax2.bar(names, pi, color=colors_all, edgecolor='black', linewidth=0.5)
ax2.set_xlabel("Project")
ax2.set_ylabel("Profitability Index (NPV/Cost)")
ax2.set_title("Profitability Index per Project")
ax2.axhline(y=np.mean(pi), color='navy', linestyle='--', linewidth=1.5, label=f'Mean PI={np.mean(pi):.2f}')
ax2.legend()
ax2.grid(True, alpha=0.3, axis='y')
for bar, v in zip(bars, pi):
    ax2.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.01,
             f'{v:.2f}', ha='center', va='bottom', fontsize=8)

# ── 5-3. Budget Allocation Pie Chart ─────────────────────────
ax3 = fig.add_subplot(2, 3, 3)
pie_labels  = selected_names + ['Remaining']
pie_values  = [costs[i] for i in selected_idx] + [BUDGET - total_cost]
pie_colors  = ['#2ecc71'] * len(selected_idx) + ['#bdc3c7']
wedges, texts, autotexts = ax3.pie(
    pie_values, labels=pie_labels, colors=pie_colors,
    autopct='%1.1f%%', startangle=140, pctdistance=0.8)
ax3.set_title(f"Budget Allocation (Total: ¥{BUDGET}M)")

# ── 5-4. DP Table Heatmap (last 10 budget steps subset) ──────
ax4 = fig.add_subplot(2, 3, 4)
# Show dp table for all projects, budget 0..BUDGET step 50
step   = 50
b_ticks = list(range(0, BUDGET + 1, step))
dp_sub  = dp_table[:, ::step]   # shape (n+1, len(b_ticks))
im = ax4.imshow(dp_sub, aspect='auto', cmap='YlOrRd', origin='upper')
ax4.set_xlabel("Budget (¥M, step=50)")
ax4.set_ylabel("Number of Projects Considered")
ax4.set_title("DP Table Heatmap (Max NPV)")
ax4.set_xticks(range(len(b_ticks)))
ax4.set_xticklabels(b_ticks, fontsize=7)
ax4.set_yticks(range(n + 1))
ax4.set_yticklabels(['0'] + names, fontsize=7)
plt.colorbar(im, ax=ax4, label='Max NPV (¥M)')

# ── 5-5. Cumulative NPV vs Budget Curve ──────────────────────
ax5 = fig.add_subplot(2, 3, 5)
budget_range = np.arange(0, BUDGET + 1)
max_npv_curve = dp_table[n, :]   # optimal NPV for each budget level
ax5.plot(budget_range, max_npv_curve, color='steelblue', linewidth=2)
ax5.axvline(x=BUDGET, color='red', linestyle='--', linewidth=1.5, label=f'Budget = ¥{BUDGET}M')
ax5.axhline(y=total_npv, color='green', linestyle='--', linewidth=1.5, label=f'Optimal NPV = ¥{total_npv}M')
ax5.scatter([BUDGET], [total_npv], color='red', s=100, zorder=5)
ax5.set_xlabel("Available Budget (¥M)")
ax5.set_ylabel("Maximum Achievable NPV (¥M)")
ax5.set_title("Optimal NPV vs Budget")
ax5.legend(fontsize=8)
ax5.grid(True, alpha=0.3)

# ── 5-6. 3D: Project Index × Budget × Max NPV ────────────────
ax6 = fig.add_subplot(2, 3, 6, projection='3d')
step3d   = 25
b_range3 = np.arange(0, BUDGET + 1, step3d)
p_range  = np.arange(0, n + 1)
B3, P3   = np.meshgrid(b_range3, p_range)
Z3       = dp_table[np.ix_(p_range, b_range3)]   # shape (n+1, len(b_range3))
surf = ax6.plot_surface(B3, P3, Z3, cmap='viridis', alpha=0.85, edgecolor='none')
ax6.set_xlabel("Budget (¥M)", fontsize=8, labelpad=6)
ax6.set_ylabel("Projects Considered", fontsize=8, labelpad=6)
ax6.set_zlabel("Max NPV (¥M)", fontsize=8, labelpad=6)
ax6.set_title("3D DP Surface\n(Budget × Projects → NPV)", fontsize=9)
fig.colorbar(surf, ax=ax6, shrink=0.5, label='NPV (¥M)')

plt.tight_layout()
plt.savefig("investment_selection.png", dpi=150, bbox_inches='tight')
plt.show()
print("Graph saved as investment_selection.png")

Code Walkthrough

Section 1 — Problem Data

Ten projects are defined with their respective costs and expected NPVs. These are stored as NumPy arrays for efficient computation.

Section 2 — Dynamic Programming Solver

This is the core algorithm. The DP table is defined as:

$$dp[i][w] = \text{maximum NPV achievable using the first } i \text{ projects with budget } w$$

The recurrence relation is:

$$dp[i][w] = \begin{cases} dp[i-1][w] & \text{if } c_i > w \ \max(dp[i-1][w],; dp[i-1][w - c_i] + v_i) & \text{if } c_i \leq w \end{cases}$$

After filling the table, back-tracking reconstructs which projects were selected by tracing which transitions changed the DP value.

Time complexity: $O(n \cdot B)$, where $n=10$ and $B=500$, making it extremely fast.

Section 3 — Results

Selected projects, total cost, total NPV, and remaining budget are printed cleanly.

Section 4 — Profitability Index

The Profitability Index (PI) is calculated as:

$$PI_i = \frac{v_i}{c_i}$$

A high PI means more NPV per yen invested — useful for intuition, though greedy PI selection doesn’t guarantee optimality for this problem.

Section 5 — Visualizations

Six subplots are generated:

Plot 1 — Cost vs NPV Scatter: Shows each project as a dot. Green = selected, Red = not selected. Reveals which projects deliver high NPV relative to cost.

Plot 2 — Profitability Index Bar Chart: Ranks projects by NPV efficiency. The dashed line marks the average PI. Notably, a high PI doesn’t always mean a project gets selected — budget constraints may force trade-offs.

Plot 3 — Budget Allocation Pie Chart: Visualizes how the ¥500M budget is distributed among selected projects and remaining slack.

Plot 4 — DP Table Heatmap: Shows the full DP table as a 2D color map. The x-axis is the budget level (step=¥50M), and the y-axis is the number of projects considered. Darker colors = higher achievable NPV, clearly showing how value accumulates.

Plot 5 — Optimal NPV vs Budget Curve: Plots the maximum achievable NPV as a function of available budget. The curve rises steeply at first then flattens — this is the efficient frontier of capital allocation.

Plot 6 — 3D Surface Plot: The most visually powerful chart. It shows the entire DP surface:

  • X-axis: budget
  • Y-axis: number of projects considered
  • Z-axis: maximum NPV

The surface illustrates how both budget and project count jointly determine the best achievable NPV, giving deep intuition into the optimization landscape.

Execution Results

=============================================
  0-1 Capital Investment Selection Result
=============================================
  Budget           : ¥500 M
  Selected Projects: ['P1', 'P2', 'P3', 'P5', 'P10']
  Total Cost       : ¥500 M
  Total NPV        : ¥635 M
  Remaining Budget : ¥0 M
=============================================


Graph saved as investment_selection.png

Key Takeaways

The DP approach guarantees the globally optimal solution — unlike greedy heuristics (e.g., always pick highest PI), it considers all valid combinations implicitly in $O(n \cdot B)$ time. For this problem:

$$\text{Optimal NPV} = \max \sum_{i \in S} v_i \quad \text{s.t.} \quad \sum_{i \in S} c_i \leq 500, \quad S \subseteq {1,\ldots,10}$$

This framework extends naturally to real-world capital budgeting scenarios with multiple budget periods, dependencies between projects, or risk-adjusted returns.