【9504】装载问题

Time Limit: 1000ms second
Memory Limit: 32m 问题描述：
有n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能中的集装箱装上轮船。

Input

第一行有2个正整数n和c，n是集装箱数，c是轮船的载重量。第二行有n个正整数，表示每个集装箱的重量

Output

计算出的最大载重量

Sample Input

5 10
7 2 6 5 4

Sample Output

10

【题解】

这是个组合问题，不要看成排列的，因为726和276是同一重量。枚举每一个是否有被装进轮船即可。

【代码】

#include <cstdio>

int n,c,a[2000],max_w = -1,sum = 0;
bool bo[2000];

void input_data()
{
    scanf("%d %d",&n,&c);
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    for (int i = 1;i <=1999;i++) //一开始所有的集装箱都能用。都能装
        bo[i] = true;
}

void sear_ch(int x)
{
    sum += a[x]; //累加重量
    bo[x] = false; //标记这个物品已经被用过
    if (sum > c) //如果总重量超过最大值 就返回上一层
        {
            sum-=a[x];
            bo[x] = true;
            return;
        }
    if (sum >max_w) //如果最大值能更新就更新
        max_w = sum;
    for (int i =x+1;i <= n;i++) //因为是组合问题 所以从x+1开始扫描
        if (bo[i])
            sear_ch(i);
    bo[x] = true; //回溯
    sum -= a[x];
}

void get_ans()
{
    for (int i = 1;i <= n;i++)
        sear_ch(i);
}

void output_ans()
{
    printf("%d",max_w);
}

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    input_data();
    get_ans();
    output_ans();
    return 0;
}