1100: B10-动态规划-集装箱装载（01背包）
时间限制: 1 Sec 内存限制: 128 MB
提交: 5 解决: 5
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

输入
第一行有2个正整数n和c。n是集装箱数，c是轮船的载重量。第2行中有n个正整数，表示集装箱的重量（0<n<10000,0<c<32767)。

输出
计算出的最大装载重量输出。

样例输入
5 10
7 2 6 5 4

样例输出
10

来源/分类
B10-动态规划

[提交] [状态]

代码：

#include<cstdio> #include<iostream> using namespace std; int a[35000]; int f[35000]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=m;j>=a[i];j--) { f[j]=max(f[j],f[j-a[i]]+a[i]); } } printf("%d\n",f[m]); return 0; }