整数变量最值：界、取整与可达性

整数约束常使连续最优点不可取。先获得界，再检查邻近整数、端点和取等构造，是许多一试与强基最值问题的基本方法。

连续界与整数界

若整数值目标 $F$ 满足 $F\le M$ ，则 $F\le\lfloor M\rfloor$ ；若 $F\ge m$ ，则 $F\ge\lceil m\rceil$ 。这只是必要的界，仍要找可行对象达到它。

严格不等式要小心：整数 $F<M$ 等价于 $F\le\lceil M\rceil-1$ ，不是始终等价于 $F\le\lfloor M\rfloor$ 。当 $M$ 本身为整数时，两种写法差一。可行域为空时不存在最大、最小值。

二次目标：检查顶点邻近整数

设 $F(k)=A(k-h)^2+C$ ， $A>0$ ，整数 $k$ 限制在闭区间 $[L,U]$ 。先取 $l=\lceil L\rceil,u=\lfloor U\rfloor$ ，若 $l>u$ 则无可行整数。

若 $h<l$ ，最小值在 $l$ ；若 $h>u$ ，在 $u$ ；若 $h\in[l,u]$ ，只需比较域内的 $\lfloor h\rfloor,\lceil h\rceil$ 。最大值则比较 $l,u$ 。 $A<0$ 时最小与最大交换角色。

例如整数 $k\in[0,10]$ 上， $3k^2-20k+40=3(k-10/3)^2+20/3$ 。比较 $k=3,4$ ，值为 $7,8$ ，所以最小值为 $7$ 。

定和平方和：相差至多一

设非负整数 $x_1,\ldots,x_m$ 的和为 $N$ ，其中 $m\ge1$ 。若某两项 $a\ge b+2$ ，把它们改成 $a-1,b+1$ ，平方和减少

a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1)>0.

因此最小值处任意两项之差不超过 $1$ 。写 $N=mq+r$ ， $0\le r<m$ ，最优配置必为 $r$ 项 $q+1$ 与 $m-r$ 项 $q$ ，故

\min\sum_{i=1}^m x_i^2=r(q+1)^2+(m-r)q^2.

上述配置确实存在，完成“下界与可达性”的双重证明。例如 $N=17,m=5$ ，取 $4,4,3,3,3$ ，最小平方和为 $59$ 。

定和乘积：连续最优点的整数修正

正整数 $a+b=N$ 、 $N\ge2$ 时， $ab\le N^2/4$ 。若 $N=2q$ ，取 $a=b=q$ ；若 $N=2q+1$ ，取 $a=q,b=q+1$ 。因此

\max ab=\left\lfloor\frac{N^2}{4}\right\rfloor.

更多正整数的定和乘积也可作平衡调整： $a\ge b+2$ 时， $(a-1)(b+1)-ab=a-b-1>0$ 。但如果允许负数、另有上下界或权重，必须重新检查调整是否保持全部约束，不能直接宣称“平均分配最优”。

关联阅读

连续界与整数界

若整数值目标

F

满足

F\le M

，则

F\le\lfloor M\rfloor

；若

F\ge m

，则

F\ge\lceil m\rceil

。这只是必要的界，仍要找可行对象达到它。

严格不等式要小心：整数

F<M

等价于

F\le\lceil M\rceil-1

，不是始终等价于

F\le\lfloor M\rfloor

。当

M

本身为整数时，两种写法差一。可行域为空时不存在最大、最小值。

定和平方和：相差至多一

设非负整数

x_1,\ldots,x_m

的和为

N

，其中

m\ge1

。若某两项

a\ge b+2

，把它们改成

a-1,b+1

，平方和减少

a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1)>0.

因此最小值处任意两项之差不超过

1

。写

N=mq+r

，

0\le r<m

，最优配置必为

r

项

q+1

与

m-r

项

q

，故

\min\sum_{i=1}^m x_i^2=r(q+1)^2+(m-r)q^2.

上述配置确实存在，完成“下界与可达性”的双重证明。例如

N=17,m=5

，取

4,4,3,3,3

，最小平方和为

59

。

定和乘积：连续最优点的整数修正

正整数

a+b=N

、

N\ge2

时，

ab\le N^2/4

。若

N=2q

，取

a=b=q

；若

N=2q+1

，取

a=q,b=q+1

。因此

\max ab=\left\lfloor\frac{N^2}{4}\right\rfloor.

更多正整数的定和乘积也可作平衡调整：

a\ge b+2

时，

(a-1)(b+1)-ab=a-b-1>0

。但如果允许负数、另有上下界或权重，必须重新检查调整是否保持全部约束，不能直接宣称“平均分配最优”。