K-優化演算法
ps：個人理解，若有錯誤還請各位大佬們糾正（最近某高校的作業涉及到了這個，是不是網上搜不到啊，嘿嘿嘿）
定義
這就是定義= =
幫助理解，廢話不多說直接上例題
例1
用1－優化法求解以下0/1背包問題，已知：n = 8, w = [16, 20, 4, 15, 25, 10, 5, 8]，p = [100, 200, 50, 90, 175, 50, 20, 60], c = 70，
解：貪心策略：按價值密度非遞減的順序檢查物品，若剩余容量能容下正在考察的物品，將其裝入；否則考慮下個物品，
用貪心法求解的程序：
效益密度為[ 6.25, 10 , 12.5 , 6 , 7 , 5 , 4 , 7.5 ]，對其排序后得到的物品順序為[ 3 , 2 , 8 , 5 , 1 , 4 , 6 , 7 ]，對應的重量為[ 4 , 20 , 8 , 25 , 16 , 15 , 10 , 5 ]，
k＝0時的計算結果為：
裝入物品3、2、8、5后，背包剩余容量為13，接下來物品1、4的重量都超過了13，考察物品6，6裝入后，背包剩余容量為3，考察物品7，其重量大于剩余容量，所以答案 x =（0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 ），得到的效益值為535，
當k＝1時的計算結果為：
先放物品3、2、8、5，得到的效益值仍為535，貪心解同上；
先放物品1，得到效益值520，貪心解為（1，1，1，1，0，0，1，1）；先放物品4，得到的效益值為520，貪心解為（1，1，1，1，0，0，1，1）；
先放物品6，得到效益值為535，貪心解為（0，1，1，0，1，1，0，1）；先放物品7，得到效益值為505，貪心解為（0，1，1，0，1，1，1），所以k優化法得到的解為（0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 ），效益值為535，
這應該算是參考答案，寫得有點抽象= =
1-優化情況比較少，我們來看看2-優化（俺的想法）
例2
題目參考例1，使用2-優化演算法
ps：很有精神，窮舉吧，，，我比較懶，，，
下面展示一些 2-優化代碼此例子使用哦，
// An highlighted block
#include <iostream>
using namespace std;
int w[8]={16,20,4,15,25,10,5,8};
int p[8]={100,200,50,90,175,50,20,60};
int r[8]={2,1,7,4,0,3,5,6};//rank 值
int sumw,sump;
int main()
{
for(int i=0;i<=6;i++){
for(int j=i+1;j<=7;j++){
int vis[8] = {0};
cout << "a" << r[i]+1 << " " << "a" << r[j]+1 << " ";
sumw = w[r[i]]+w[r[j]];
sump = p[r[i]]+p[r[j]];
vis[r[i]]=vis[r[j]]=1;
for(int k = 0;k <= 7; k++){
if(!vis[r[k]]){
if((sumw+w[r[k]])<=70){sumw+=w[r[k]];sump+=p[r[k]];vis[r[k]]=1;cout << "a" << r[k]+1 << " ";}
}
}
cout << " " << sump << endl;
}
}
return 0;
}
運行結果
= =水啊水,還是那句話，若理解有誤，請給學渣指出來，跪謝查閱的大佬們~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/224304.html
標籤：其他
上一篇：三極管的基本狀態分析