NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2018高中組決賽
 E. 背包問題

作者 主題: E. 背包問題  (閱讀 41 次)

lose

  • 新手
  • *
  • 文章數: 14
    • 檢視個人資料
E. 背包問題
« 於: 十二月 08, 2019, 04:53:27 pm »

題目要求:可分割價值的物品,一旦要分割有額外的花費

參考概念:
轉換成數形幾何去思考,X 軸為重量,Y 軸為價值,我們會得到一個 X、Y 嚴格遞增的單調曲線。若我們從前 i 個物品的曲線推到前 i+1 個物品的曲線,可以知道是兩個曲線的最大值,而放入這第 i+1 個物品的曲線是前一個曲線配上 Minkowski Sum 的結果。只看這一個物品的曲線,也是一個單調遞增的曲線。

仔細推敲兩個合併的結果,可以發現不論怎麼取最大值、疊合曲線,每一個曲線上的線段都恰好對應到一個物品的分割或不分割。因此最佳解至多有一個物品被分割。那麼窮舉會分割的物品,時間複雜度落於 O(n^2 m)。

離上一次參與已離七年有餘,礙於沒地方測試,可能會 TLE 的代碼如下

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;

struct Item {
int w, v, c;
bool operator<(const Item &o) const {
return w < o.w;
}
};

int main() {
int n;
int m;
Item items[2005];
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 1; i <= n; i++)
assert(scanf("%d %d %d", &items[i].w, &items[i].v, &items[i].c) == 3);

double ans = 0;
static int dpBase[2005][10005] = {};
for (int j = 1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = 0; k <= m; k++) {
dpBase[j][k] = dpBase[j-1][k];
if (k >= w)
dpBase[j][k] = max(dpBase[j][k], dpBase[j-1][k-w] + v);
}
}
for (int i = 0; i <= m; i++)
ans = max(ans, (double) dpBase[n][i]);
for (int i = 1; i <= n; i++) {
if (items[i].v <= items[i].c)
continue;
static int dp[10005];
memcpy(dp, dpBase[i-1], sizeof(dp[0])*(m+1));
for (int j = i+1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = m; k >= w; k--)
dp[k] = max(dp[k], dp[k-w] + v);
int same = memcmp(dp, dpBase[j], sizeof(dp[0])*(m+1));
if (same == 0) {
memcpy(dp, dpBase[n], sizeof(dp[0])*(m+1));
break;
}
}

for (int j = 0; j <= m; j++) {
double val = dp[j];
if (m-j >= items[i].w) {
val += items[i].v;
} else {
double cwv = (double) (m-j) / items[i].w * items[i].v - items[i].c;
if (cwv > 0)
val += cwv;
}
ans = max(ans, val);
}
}
printf("%.20lf\n", ans);
}
return 0;
}
« 上次編輯: 十二月 08, 2019, 06:30:37 pm 由 lose »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2018高中組決賽
 E. 背包問題