Nonlinear model predictive control (NMPC) suffers from problems of closed loop instability and huge computational burden, which greatly limit its applications in real plants. In this paper, a new NMPC algorithm, whose stability is robust with respect to regulable computational cost, is presented. First, a new generalized pointwise min-norm (GPMN) control, as well as its analytic form considering a super-ball type input constraint, is given. Second, the GPMN controller is integrated into a normal NMPC algorithm as a structure of control input profile to be optimized, called GPMN enhanced NMPC (GPMN-ENMPC). Finally, a numerical example is presented and simulation results exhibit the advantage of the GPMN-ENMPC algorithm: computational cost can be regulated according to the computational resources with guaranteed stability.