有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。\n\n输入\n第一行有2个正整数n和

c，表示集装箱数量和轮船载重量。接下来一行有n个正整数，表示每个集装箱的重量wi。

输出
输出一个整数，表示轮船最多能装载的重量。

样例输入
5 10
2 3 5 4 1

样例输出
10

解释：最优方案是将重量为5、4、1的三个集装箱装上轮船，总重量为10。

相关问题

有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi。找出一种最优

要找出一种最优的方案，以将n个集装箱装上载重量为c的轮船，其中集装箱i的重量为wi。我们可以采用动态规划的方法来解决这个问题。

首先，我们定义一个二维数组dp，其中dp[i][j]表示只考虑前i个集装箱，且船的载重量为j时，可以装载的最大重量。

接下来，我们利用动态规划的思想，从前往后依次填充dp数组。具体的状态转移方程如下：

1. 当i=0时，即没有集装箱可选择时，dp[0][j]的值都应为0。
2. 当j=0时，即船的载重量为0时，dp[i][0]的值都应为0。
3. 当i≥1且j≥1时，分为两种情况讨论：
a. 若集装箱i的重量wi大于船的载重量j时，则该集装箱无法装载到船上，故dp[i][j] = dp[i-1][j]。
b. 若集装箱i的重量wi小于等于船的载重量j时，则该集装箱可以选择装载或不装载到船上，比较两种情况下的最优解，即
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + wi)。

最后，dp[n][c]即为所求的最优解，即装载到船上的最大重量。

通过以上的动态规划算法，我们可以找出一种最优的装载方案，以将n个集装箱装上载重量为c的轮船，并计算出最大装载重量。

最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。轮船装载体积不受限制。问如何选择集装箱，使得装入轮船的集装箱数量最多？请用贪心法实现最优装载问题。

### 回答1：
最优装载问题是指在给定轮船载重量c和一批集装箱，每个集装箱的重量为wi，要求选择尽可能多的集装箱装上轮船。这个问题可以用贪心算法来解决。

具体实现方法如下：

1. 将所有集装箱按照重量从大到小排序。

2. 从重量最大的集装箱开始，依次尝试将其装入轮船，直到轮船的剩余载重量小于该集装箱的重量为止。

3. 将下一个重量次大的集装箱尝试装入轮船，重复步骤2，直到所有集装箱都被尝试过。

4. 统计成功装入轮船的集装箱数量，即为最优解。

这个贪心算法的正确性可以通过反证法证明。假设存在一种更优的装载方案，使得装入轮船的集装箱数量比上述算法得到的结果更多。那么在这个更优的方案中，一定存在一个集装箱，它的重量比上述算法中被尝试的第一个无法装入轮船的集装箱的重量更小。因此，如果按照上述算法的顺序尝试装载集装箱，这个更轻的集装箱一定能够被成功装入轮船，与假设矛盾。因此，上述算法得到的结果是最优解。

### 回答2：
最优装载问题是一种经典的优化问题，用于求解在限制条件下选择最优解的问题。在此问题中，我们需要在轮船的载重量限制下，尽可能地装载更多的集装箱。

贪心法是解决最优装载问题的一种有效算法。贪心算法的基本思想是，在每一步中选择当前状态下最优的解，最终得到全局最优解。

在最优装载问题中，我们可以按照以下步骤实现贪心算法：

1. 将所有集装箱按照重量wi从大到小排序，表示尽可能选择重量大的集装箱来装载。

2. 从排序后的集装箱列表中按顺序选择集装箱，如果当前已经选择的集装箱总重量cw加上当前要选择的集装箱重量wi小于等于轮船载重量c，则选择该集装箱装入轮船，并将当前已经选择的集装箱总重量cw加上wi。

3. 如果当前已经选择的集装箱总重量cw加上当前要选择的集装箱重量wi大于轮船载重量c，则该集装箱无法装入轮船，继续选择下一个集装箱。

4. 重复步骤2和步骤3，直到所有集装箱都被考虑。

5. 输出已装载集装箱的数量。

通过这样的贪心策略，我们可以实现最优装载问题并得到最优解。

需要注意的是，贪心算法的局限性在于它只能得到局部最优解，不一定能得到全局最优解。在某些情况下，贪心算法可能会失效，例如，当集装箱的重量分布不均时，贪心算法可能无法得到最优解。因此，在实际应用中，需要根据具体情况选择合适的算法来求解。

### 回答3：
最优装载问题，即在有限的载重量条件下最大化装箱数量的问题，可以采用贪心法进行求解。

首先，我们需要确定每个集装箱的单位重量价值，即按照每吨货物所占用的轮船空间的价值确定。这样，我们就能够依据集装箱单位重量的价值从高到低排序。

接下来，我们按照排序后的顺序依次选择集装箱进行装载。每次选择重量较小的集装箱放在尽量靠前的位置，直到轮船的载重量达到极限或全部集装箱都已经装载完毕。

贪心法的实现思路是在将集装箱按照单位重量价值排序后，依次选择重量较小的集装箱进行装载。因为重量较小的集装箱对于轮船的载重量贡献较小，可以给后续装载留出更多的余地，从而使得装载的集装箱数量更多。

同时，由于轮船的装载体积没有受到限制，因此不需要考虑集装箱的体积问题，只需按照重量排序即可。

通过贪心法，我们可以快速解决最优装载问题，并找出一种使得装入轮船的集装箱数量最多的装载方案。