Packaging is usually a multi-object manipulation task involving objects of different softness and dimensions. The flexibility of paper and the variety of shoe types and states are major challenges for packaging tasks. In this study, we propose a complete solution for a shoe packaging task involving paper, which makes full use of extrinsic resources to improve its efficiency. Firstly, according to the different characteristics of the manipulated objects and task requirements, visual perception is developed to obtain the grasp poses of different objects. Furthermore, paper grasping strategies by exploiting environmental constraints and shoe reorientation method with gravity are proposed, which are necessary for a shoe packaging task. Finally, the complete pipeline for a shoe packaging task is introduced and qualitative and quantitative experiments verify its feasibility and robustness.