算法设计与分析

题目：

描述：

有两艘船，载重量分别是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

来源：

tips：

求出c1 的bestw，如果r - bestw < c2 输出Yes

否则：：：：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int n,c1,c2,w[15];

int cw,bestw,r,x[15],bestx[15];

void backtrack(int i)

{

if(i > n) {

if(cw > bestw) bestw = cw;

return;

}

else {

r -= w[i];

if(cw + w[i] <= c1)

{

cw += w[i];

backtrack(i + 1);

cw -= w[i];

}

if(cw + r > bestw)

backtrack(i + 1);

r += w[i];

}

}

int main()

{

while(cin >> c1 >> c2 >> n && n)

{

cw = 0;

bestw = 0;r = 0;

for(int i = 1;i <= n;i ++)

{

cin >> w[i];

r += w[i];

}

backtrack(1);

if(r - bestw <= c2) cout << "Yes" << endl;

else cout << "No" << endl;

}

return 0;

}