贪心和回溯法解2船最优装载问题

问题描述

有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。

问题分析

如果给定一个装载问题有解，则采用下面的策略可得到最优装载方案：
（1）首先将第一艘轮船尽可能装满；
（2）将剩余的集装箱装上第二艘轮船。

#include<stdio.h>    
#define max 12;   
int c1,c2,n;   //载重量分别是c1、 c2，n个集装箱
int weight;   
int best;   
int boxw[12];   
void backtrack(int a)   
{   
    if(a==n)   
    {   
        if(weight>best)   
            best=weight;   
        return ;   
    }   
    if(weight+boxw[a]<=c1)   
    {   
        weight=weight+boxw[a];   
        backtrack(a+1);   
        weight=weight-boxw[a];   
    }   
    backtrack(a+1);   
}          
int main()   
{   
    while(1)   
    {   
        int sum=0;   
        printf("请分别输入两艘船的载重量及集装箱的个数:\n");
        scanf("%d %d %d",&c1,&c2,&n);
        if(c1==0&&c2==0&&n==0)   
            break;   
        for(int i=0;i<n;i++)   
        {   
            scanf("%d",&boxw[i]);
            sum+=boxw[i];   
        }   
        best=weight=0;   
        backtrack(0);   
        if(sum-best<=c2)    
            printf("Yes\n");
        else   
            printf("No\n");  
    }   
    return 0;   
}