• 问题描述：
  • 在n个集装箱要装上重为W的船，集装箱i的重量 wi。
  • 将尽可能重的集装箱装上船，当重量相同时，取集装箱个数尽量少。
• 要求：

1. 采用回溯法
2. 采用剪枝条件
   • 左孩子：只装载满足重量的集装箱
   • 右孩子：至少要选3个集装箱

#include 
    
     #include 
     
      #include 
      
       #define MAXN 20  //最多集装箱个数int n, W, int maxw;        //maxw：存放最优解的总重量       int x[MAXN];     //x：存放最优解向量int minm = 32767;  //minm：存放最优解的集装箱个数，初始为最大值 //考虑第i个集装箱，tw为考虑第i个集装箱时装入的总重量，其装载解向量为op void Loading(int w[], int tw, int m, int op[], int i){    int j;    if(i > n){  //找到一个叶子节点         if(tw <= W && (tw > maxw || (tw == maxw && m < minm))) {            maxw = tw;            minm = tw;            for(j=1; j<=n; j++){                x[j] = op[j];            }        }    } else {  //尚未找完所有物品        op[i] = 1;  //选取第i个集装箱         if(tw + w[i] <= W)  //左孩子节点剪枝：装载满足条件的集装箱             Loading(w, tw+w[i], m+1, op, i+1);        op[i] = 0;   //不选取第i个集装箱，回溯         if(m <= 2) //右孩子剪枝：至少要选3个集装箱             Loading(w, tw, m, op, i+1);    }}void dispSolution(int n){    int i;    printf("选取的集装箱：\n");    for(i=0; i<=n; i++){        if(x[i]==1)            printf("  选取第 %d 个集装箱\n",i);    }    printf("总重量 = %d\n",maxw);} int main(){    int w[] = {0,5,2,6,4,3};  //各集装箱重量，不用下标0的元素     int op[MAXN];  //存放临时解     n = 5, W = 10;    Loading(w, 0, 0, op, 1);    dispSolution(n); }