装载问题

问题描述

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

输入

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

输出

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

样例输入

样例输出

Yes
No

解题思路

先计算出 c1 能放下的最大值 max , 若 c2-max >= 0 ,则能装下.

公式

\( f(c,n) = min\{f(c,n-1),f(c-w[n],n-1)\} \)

其中 w 为 weight 集合.

公式计算背包容量剩余c,且剩余n个物品时, 最优解剩余的背包容量.

递归终点

物品数为0,或者背包装不下

我的代码

#include<iostream>
#define NaN 114514

using namespace std;

int min(int,int);
int f(int,int,int[]);

int main(){
    while(1){
        // sum 物品重量总和, weight 记录装入c1的最大值.
        int c1,c2,n,sum = 0,weight;
        cin >> c1 >> c2 >> n;
        if( n == 0 ){
            break;
        }
        int w[n];
        for(int i = 0; i < n; i++){
            cin >> w[i];
            sum += w[i]; // 计算中重量
        }
        weight = c1 - f(c1,n,w); // 装入c1的总重量
        if( sum - weight <= c2 ){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}

int min(int a,int b){
    return a<b?a:b;
}

int f(int c,int n,int w[]){
    if( c < 0 ){ // 如果装不下
        return NaN; // 返回无穷大
    }
    if( n == 0 ){ // 如果没有物品了
        return c; // 直接返回背包剩余容量
    }
    int i = n-1; //下标
    return min(f(c,n-1,w),f(c-w[i],n-1,w));
}