題目連結:https://syzoj.com/problem/114521
記憶體限制:512 MiB 時間限制:1000 ms
題目描述
有一批共n個集裝箱要裝上艘載重量為c的輪船,其中集裝箱i的重量為wi。找出一種最優裝載方案,将 輪船盡可能裝滿,即在裝載體積不受限制的情況下,将盡可能重的集裝箱裝上輪船。
輸入格式
第一行有2個正整數n和c。n是集裝箱數,c是輪船的載重量。 接下來的1行中有n個正整數,表示集裝箱的重量。
輸出格式
将計算出的最大裝載重量輸出
輸入樣例
5 10
7 2 6 5 4
輸出樣例
資料範圍與提示
解題思路
#include <iostream>
using namespace std;
int w[1005], dp[1005];
int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 0; i < n; i++)
cin >> w[i];
for (int i = 0; i < n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
cout << dp[m] << endl;
}
return 0;
}