【題目鏈接】

ybt 1225：金銀島
OpenJudge NOI 4.6 1797:金銀島

【題目考點】

1. 貪心

2. 部分背包問題

【解題思路】

該題為部分背包問題

1. 貪心選擇性質的證明：

貪心選擇：每次盡量多地選擇單位價值最高的金屬
單位價值：金屬的價值除以重量，即$v_i/n_i$

證明：存在最優解包含第一次貪心選擇

假設對于所有最優解，都不包含第一次的貪心選擇。
即假設單位價值最高的金屬為g，存在重量為w的金屬g沒有被選擇，不在最優解中。
在最優解中選擇重量為w的金屬（也許是幾種金屬），這部分金屬的價值為$v_a$，重量為w的金屬g的價值為$v_g$，因為金屬g的單位價值最高，所以一定有$v_g\ge v_a$。用重為w的金屬g替換最優解中重為w的金屬，此時這些選擇的金屬包含貪心選擇，價值不會比替換前減少，也是最優解，這與假設相悖，假設不成立，原命題得證。

證明：前k次都進行貪心選擇，最優解包含第k+1次貪心選擇

假設對于所有最優解，都不包含第k+1次的貪心選擇。
即假設此時剩下的金屬中單位價值最高的金屬為g，如果做貪心選擇，可以選擇重量為w的金屬g。但最優解沒有做貪心選擇，說明最優解中存在至少重量為w的單位價值等于或低于金屬g的金屬。
在最優解中選擇重量為w的單位價值等于或低于金屬g的金屬，這部分金屬的價值為$v_a$，重量為w的金屬g的價值為$v_g$，因為金屬g的單位價值最高，所以一定有$v_g\ge v_a$。用重為w的金屬g替換最優解中重為w的金屬，此時這些選擇的金屬包含貪心選擇，價值不會比替換前減少，也是最優解，這與假設相悖，假設不成立，原命題得證。

2. 具體做法

將所有金屬按單位價值$v_i/n_i$降序排序，順序遍歷

• 如果該金屬重量小于等于剩余可放重量，那么選擇該金屬的全部重量，統計其價值。
• 如果該金屬重量大于剩余可放重量，那么選擇該金屬的重量為：剩余可放重量，統計這部分金屬的價值。

輸出選擇的金屬的總價值。

【題解代碼】

解法1：貪心

#include<bits/stdc++.h> using namespace std; #define N 105 struct Metal {double n, v; }; bool cmp(Metal a, Metal b) {return a.v/a.n > b.v/b.n; } int main() {int k, w, s;Metal m[N];cin >> k;while(k--){double totVal = 0;cin >> w >> s;for(int i = 1; i <= s; ++i)cin >> m[i].n >> m[i].v;sort(m+1, m+1+s, cmp);for(int i = 1; i <= s; ++i){if(w >= m[i].n)//w:剩余可放重量 {totVal += m[i].v;w -= m[i].n;}else{totVal += m[i].v/m[i].n*w;break;}}cout << fixed << setprecision(2) << totVal << endl;}return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1225：金银岛 | OpenJudge NOI 4.6 1797:金银岛的全部內容，希望文章能夠幫你解決所遇到的問題。

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