b184: 5. 裝貨櫃問題

題目連結: https://zerojudge.tw/ShowProblem?problemid=b184

# 內容

現在一共有若干項貨品可選擇運載，每一項 k 都有一個已知的體積 v [k]，以及載運的利潤 c [k]，但是貨櫃的總容量是 100，可能無法將貨物全部裝入，希望選出其中的若干項，其體積總和不超過 100，使得利潤最大。（每一項貨物的體積為 1~100 的整數，而利潤是 1~60000 的整數。）

# 解題思路

就是經典的 01 背包問題，但是，我稍微改寫了一下，使每一次讀入之後，就直接讓其找出選或不選的最大值。

# 程式碼

#include<bits/stdc++.h>

using namespace std;

int main() {

	int t, DP[101], v, p;

	while (cin >> t) {

		memset(DP, 0, sizeof(DP));

		while (t--) {

			cin >> v >> p;

			for (int i = 100; i >= v; --i)

				DP[i] = max(DP[i], DP[i - v] + p);

		}

		cout << DP[100] << '\n';

	}

}