时限：1000ms 内存限制：10000K  总时限：3000ms

描述

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

 

输入

多个测例，每个测例的输入占两行。第一行一次是c1、c2和n（n<=10）；第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。

 

输出

对于每个测例在单独的一行内输出Yes或No。

 

输入样例

7 8 2

8 7

7 9 2

8 8

0 0 0

 

输出样例

Yes

No

装载问题同样也是递归回溯法的一个简单应用，用子集树表示解空间显然是最合适的。在递归回溯时，可以进行相应的剪枝。问题的解要满足两个条件：

1.首先将第一艘轮船尽可能装满

2.将剩余的集装箱装上第二艘轮船

由此可知，只要求出不超过第一艘轮船载重量c1的最大值，若总重量-c1<=c2则可以装上两艘船。

/** @author Panoss*/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;#define DBG 1#define fori(i,a,b) for(int i = (a); i < (b); i++)#define forie(i,a,b) for(int i = (a); i <= (b); i++)#define ford(i,a,b) for(int i = (a); i > (b); i++)#define forde(i,a,b) for(int i = (a); i >= (b); i++)#define forls(i,a,b,n) for(int i = (a); i != (b); i = n[i])#define mset(a,v) memset(a, v, sizeof(a))#define mcpy(a,b) memcpy(a, b, sizeof(a))#define dout DBG && cerr << __LINE__ << " >>| "#define checkv(x) dout << #x"=" << (x) << " | "<
               
                > x#define MIN_LD -2147483648#define MAX_LD 2147483647#define MIN_LLD -9223372036854775808#define MAX_LLD 9223372036854775807#define MAX_INF 18446744073709551615inline int reint() { int d; scanf("%d",&d); return d; }inline long relong() { long l; scanf("%ld",&l); return l; }inline char rechar() { scanf(" "); return getchar(); }inline double redouble() { double d; scanf("%lf", &d); return d; }inline string restring() { string s; cin>>s; return s; }int c1, c2, n, W[15];int current_weight, best_weight, residue_weight, total_weight;void init(){　　mset(W, 0);　　current_weight = 0;　　best_weight = 0;　　total_weight = 0;}void DFS(int depth) {　　if(depth > n)　　{　　　　best_weight = max(best_weight, current_weight);　　　　return ;　　}　　residue_weight -= W[depth];　　if(current_weight + W[depth] <= c1) //搜索左子树　　{　　　　current_weight += W[depth];　　　　DFS(depth + 1);　　　　current_weight -= W[depth]; //回溯时一定要改回来,因为状态不改变　　}　　if(current_weight + residue_weight > best_weight) //搜索右子树，注意剪枝　　　　DFS(depth+1);　　residue_weight += W[depth];}int main(){　　//freopen("data.txt","r",stdin);　　while(scanf("%d%d%d",&c1,&c2,&n)==3&&(c1+c2+n))　　{　　　　init();　　　　forie(i,1,n)　　　　{　　　　　　scanf("%d",&W[i]);　　　　　　total_weight += W[i];　　　　}　　　　residue_weight = total_weight;　　　　DFS(1);　　　　if(total_weight - best_weight <= c2)　　　　　　cout << "Yes" << endl;　　　　else　　　　　　cout <<"No" << endl;　　}　　return 0;}