題目描述：

給定n個物品的重量和兩艘載重量分別為c1和c2的船，問能否用這兩艘船裝下所有的物品。

?

思路

1. 樸素背包問題

2. 有幾個細節要好好把握 (1) 在讀入物品重量時順帶統計物品的最大值和總重量 (2) 對載重量較小的船計算dp

3. 一維 dp, dp[i] 表示總物品重量為 i 時的最大價值, 因此 dp[i] 是不連續的, 統計結果時需要遍歷 dp. 而二維 dp[][] 則可以填滿矩陣

?

代碼 未通過九度測試

#include <iostream> #include <stdio.h> #include <memory.h> using namespace std;int n, c1, c2; int wet[200]; int dp[10000];int main() {while(scanf("%d%d%d", &n, &c1, &c2) != EOF) {int totalWeight = 0;bool exceed = false;int biggerone = max(c1, c2);for(int i = 0; i < n; i ++) {scanf("%d", wet+i);totalWeight += wet[i];if(wet[i] > biggerone) {exceed = true;}}if(exceed) {cout << "NO" << endl;continue;}int c = min(c1, c2);memset(dp, 0, sizeof(int)*totalWeight);for(int i = 0; i < n; i ++) {for(int v = c; v >= wet[i]; v --) {dp[v] = max(dp[v], dp[v-wet[i]]+wet[i]);}}int carryone;for(int i = 0; i <= c; i ++)carryone = max(carryone, dp[i]);if(biggerone >= totalWeight-carryone)cout << "YES" << endl;elsecout << "NO" << endl;}return 0; }

?

轉載于:https://www.cnblogs.com/xinsheng/p/3586984.html

總結

以上是生活随笔為你收集整理的九度 1462：两船载物问题(01背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。