放置階段我用動態規劃算法，java源碼如下：

import java.util.ArrayList;
/**輸入：服務器規格、虛擬機規格及預測數目、要優化資源維度
* 輸出：放置結果和預測結果，以給定字符串形式返回
* @author wenj16
*/
public class DP {
/**輸入參數
* bag 服務器類
* predictEcs 預測的虛擬機規格和數目，已經被處理成一個列表
* optResource 需要優化的資源維度，有CPU和MEM
*/
Bag bag;
ArrayList<Ecs> predictEcs;
String optResource;
/**中間變量和輸出參數
* 注意：題目要求的是返回一個字符串數組
* c 動態規劃每個點的最優值
* em 動態規劃每個點消耗的內存
* record 記錄每個點的上一個點
* cpu 動態規劃每個點消耗的cpu，c、em、cpu可能編的有點多余，但是不影響
* x 記錄每個物品是否被裝進背包
* bagNum 開的背包個數
* secResult 返回第二階段結果，是一個數列，每個元素存放一個背包裝載情況
* totalNum 第一階段虛擬機總預測數
* finalRes 最終結果
*/
int[][] c;
int[][] em;
int[][] record;
int[][] cpu;
int[] x;
int bagNum;
int totalNum;
ArrayList<String> secResult = new ArrayList<String>();
String[] finalRes;
/**我用一個一維數組backup備份預測階段各個虛擬機的數目,用于修改第一階段的預測結果
*
*/
int[] backup;
DP(ArrayList<Ecs> predictInfo,String optResource,Bag bag){
this.predictEcs=predictInfo;
this.optResource=optResource;
this.bag=bag;
}
/**動態規劃解這個背包問題
* 可能會開若干個非常大的數組，用來迭代計算，內存占用比較大，要想辦法優化
*/
public void init() {
//備份虛擬機預測數目到backup數組
backup=new int[predictEcs.size()];
for(int i=0;i<backup.length;i++) {
backup[i]=predictEcs.get(i).num;
}
//將內存統一除以1024
for(int i=0;i<predictEcs.size();i++) {
predictEcs.get(i).eme/=1024;
}
//計算背包cpu
int maxCPU= bag.cpuCap;
//計算背包內存
int maxEM=bag.emeCap ;
//-------------------------------------------_-_--------------------優化cpu-------------------------------
if(this.optResource.equalsIgnoreCase("CPU")) {
//要優化資源維度是cpu
boolean flag=true;
while(flag==true) {
flag=false;
//動態規劃
//計算預測的虛擬機數目
int goodNum=0;
for(int i=0;i<predictEcs.size();i++) {
goodNum+=predictEcs.get(i).num;
}
//初始化矩陣
c=new int[goodNum+1][maxCPU+1];
em=new int[goodNum+1][maxCPU+1];
//記錄上一個點
record=new int[goodNum+1][maxCPU+1];
//依次遍歷每個虛擬機
for(int i=1;i<=goodNum;i++) {
//計算i屬于第幾個flavor
int type=0;
int sum=0;
for(int j=0;j<predictEcs.size();j++) {
sum+=predictEcs.get(j).num;
if(i<=sum) {
type=j;//j=0 屬于flavor1
break;
}
}
//依次遍歷每個cpu
for(int j=1;j<=maxCPU;j++) {
//狀態轉移方程
if(predictEcs.get(type).cpu <= j) {//背包可能裝下j
if(predictEcs.get(type).cpu +c[i-1][j - predictEcs.get(type).cpu] > c[i-1][j]) {//裝下價值更大
if(predictEcs.get(type).eme + em[i-1][j - predictEcs.get(type).cpu] <= maxEM) {//內存也不違背
c[i][j] = predictEcs.get(type).cpu + c[i-1][j - predictEcs.get(type).cpu];
em[i][j] = predictEcs.get(type).eme + em[i-1][j - predictEcs.get(type).cpu];
record[i][j]=j - predictEcs.get(type).cpu;
}else if(predictEcs.get(type).eme + em[i-1][j - predictEcs.get(type).cpu] > maxEM) {//能夠裝下但是內存會違背
c[i][j] = c[i-1][j];
em[i][j] = em[i-1][j];
record[i][j]=j;
for(int k=j-1;k>=0;k--) {//遍歷看上一步哪個點內存不違背而且價值更大
if(em[i-1][k]+predictEcs.get(type).eme<=maxEM && c[i-1][k]+predictEcs.get(type).cpu>c[i-1][j]) {
c[i][j]=c[i-1][k]+predictEcs.get(type).cpu;
em[i][j]=em[i-1][k]+predictEcs.get(type).eme;
record[i][j]=k;//記錄下這個位置
break;
}
}
}
}
else {
c[i][j] = c[i-1][j];
em[i][j] = em[i-1][j];
record[i][j]=j;
}
}else {
c[i][j] = c[i-1][j];
em[i][j] = em[i-1][j];
record[i][j]=j;
}
}
}
//反向逆推獲得背包物品
boolean[] x = new boolean[goodNum+1];
int cpuTemp=maxCPU;
for(int i=goodNum;i>0;i--) {
if(record[i][cpuTemp]==cpuTemp)
x[i]=false;
else {
x[i]=true;
//計算i屬于第幾個flavor
int type=0;
int sum=0;
for(int j=0;j<predictEcs.size();j++) {
sum+=predictEcs.get(j).num;
if(i<=sum) {
type=j;
break;
}
}
cpuTemp=record[i][cpuTemp];
}
}
//返回一個背包裝載結果
String oneBagResult = "";
int[] flavorNums=new int[predictEcs.size()];
int index=1;
for(int i=0;i<predictEcs.size();i++) {
int temp =predictEcs.get(i).num;
if(temp!=0) {
int total=0;
for(int j=index;j<index+temp;j++) {
if(x[j]==true) {
total+=1;
//資源扣減
predictEcs.get(i).num--;
}
}
index+=temp;
if(total!=0) {
oneBagResult = oneBagResult + predictEcs.get(i).name + " " + total + " ";//flavor1 1 flavor2 0 flavor3 0
flavorNums[i]=total;
}
}
}
//將背包放入列表
secResult.add(oneBagResult);
bagNum++;
//判斷剩下資源有足夠一個背包的資源，有就再開一個
boolean flag2=true;
while(flag2==true) {
for(int i=0;i<predictEcs.size();i++) {
if(predictEcs.get(i).num<flavorNums[i]) {
flag2=false;
break;
}
}
if(flag2==true) {
secResult.add(new String(oneBagResult));
bagNum++;
for(int i=0;i<predictEcs.size();i++) {
predictEcs.get(i).num-=flavorNums[i];
}
}
}
/**計算背包資源總數，如果小于一個背包的15%，修改備份backup中的預測數，同時將所有虛擬機設置為0
* 同時還得重新計算預測虛擬機總數
*/
double restResources=0;
for(int i=0;i<predictEcs.size();i++) {
restResources=restResources+predictEcs.get(i).num*predictEcs.get(i).cpu;
}
if(restResources<0.15*bag.cpuCap) {
for(int i=0;i<backup.length;i++) {
backup[i]-=predictEcs.get(i).num;//修改第一階段預測數目
predictEcs.get(i).num=0;//該虛擬機數目設置為0
}
//重新計算第一階段虛擬機總的預測數目
totalNum=0;
for(int i=0;i<backup.length;i++) {
totalNum+=backup[i];
}
}
//下一次背包循環
for(int i= 0;i<predictEcs.size();i++) {
if(predictEcs.get(i).num!=0) {
flag=true;
break;
}
}
}
//-------------------------------------------_-_--------------------優化內存------------------------------
}else if(this.optResource.equalsIgnoreCase("MEM")) {
//計算背包內存
maxEM=bag.emeCap;
boolean flag=true;
while(flag==true) {
flag=false;
//計算預測的虛擬機數目
int goodNum=0;
for(int i=0;i<predictEcs.size();i++) {
goodNum+=predictEcs.get(i).num;
}
//初始化矩陣
c=new int[goodNum+1][maxEM+1];
cpu=new int[goodNum+1][maxEM+1];
record=new int[goodNum+1][maxEM+1];
//依次遍歷每個虛擬機
for(int i=1;i<=goodNum;i++) {
//計算i屬于第幾個flavor
int type=0;
int sum=0;
for(int j=0;j<predictEcs.size();j++) {
sum+=predictEcs.get(j).num;
if(i<=sum) {
type=j;
break;
}
}
//依次遍歷每個eme
for(int j=1;j<=maxEM;j++) {
if(predictEcs.get(type).eme <= j) {

if(predictEcs.get(type).eme +c[i-1][j - predictEcs.get(type).eme] > c[i-1][j]) {

if(predictEcs.get(type).cpu + cpu[i-1][j - predictEcs.get(type).eme] <= maxCPU) {
c[i][j] = predictEcs.get(type).eme + c[i-1][j - predictEcs.get(type).eme ];
cpu[i][j] = predictEcs.get(type).cpu + cpu[i-1][j - predictEcs.get(type).eme];
record[i][j]=j - predictEcs.get(type).eme;

}else if(predictEcs.get(type).cpu + cpu[i-1][j - predictEcs.get(type).eme] > maxCPU) {
c[i][j] = c[i-1][j];
cpu[i][j] = cpu[i-1][j];
record[i][j]=j;
for(int k=j-1;k>=0;k--) {
if(cpu[i-1][k]+predictEcs.get(type).cpu<=maxCPU && c[i-1][k]+predictEcs.get(type).eme>c[i-1][j]) {
c[i][j]=c[i-1][k]+predictEcs.get(type).eme;
cpu[i][j]=cpu[i-1][k]+predictEcs.get(type).cpu;
record[i][j]=k;
break;
}
}
}
}

else {
c[i][j] = c[i-1][j];
cpu[i][j] = cpu[i-1][j];
record[i][j]=j;
}

}else {
c[i][j] = c[i-1][j];
cpu[i][j] = cpu[i-1][j];
record[i][j]=j;
}
}

}
//反向逆推獲得背包物品
boolean[] x = new boolean[goodNum+1];
int emeTemp=maxEM;
for(int i=goodNum;i>0;i--) {
if(record[i][emeTemp]==emeTemp)//bug鍦ㄨ繖
x[i]=false;
else {
x[i]=true;
//計算i屬于第幾個flavor
int type=0;
int sum=0;
for(int j=0;j<predictEcs.size();j++) {
sum+=predictEcs.get(j).num;
if(i<=sum) {
type=j;
break;
}
}

emeTemp=record[i][emeTemp] ;
}
}
//返回一個背包裝載結果
String oneBagResult = "";
int[] flavorNums=new int[predictEcs.size()];
int index=1;
for(int i=0;i<predictEcs.size();i++) {
int temp =predictEcs.get(i).num;
if(temp!=0) {
int total=0;
for(int j=index;j<index+temp;j++) {
if(x[j]==true) {
total+=1;
//資源扣減
predictEcs.get(i).num--;
}
}
index+=temp;
if(total!=0) {
oneBagResult = oneBagResult + predictEcs.get(i).name + " " + total + " ";
flavorNums[i]=total;
}
}
}
//將背包放入列表
secResult.add(oneBagResult);//bug 瑙ｅ嚭涓�涓┖鑳屽寘
bagNum++;
//剩余資源是否有相同背包，有就新開同樣的背包并做資源扣減
boolean flag2=true;
while(flag2==true) {
for(int i=0;i<predictEcs.size();i++) {
if(predictEcs.get(i).num<flavorNums[i]) {
flag2=false;
break;
}
}
if(flag2==true) {
secResult.add(new String(oneBagResult));
bagNum++;
for(int i=0;i<predictEcs.size();i++) {
predictEcs.get(i).num-=flavorNums[i];
}
}
}
/**計算背包資源總數，如果小于一個背包的15%，修改備份backup中的預測數，同時將所有虛擬機設置為0
* 同時還得重新計算預測虛擬機總數
*/
double restResources=0;
for(int i=0;i<predictEcs.size();i++) {
restResources=restResources+predictEcs.get(i).num*predictEcs.get(i).eme;//內存的情況單位得注意一下
}
if(restResources<0.15*bag.emeCap) {
for(int i=0;i<backup.length;i++) {
backup[i]-=predictEcs.get(i).num;//修改第一階段預測數目
predictEcs.get(i).num=0;//該虛擬機數目設置為0
}
//重新計算第一階段虛擬機總的預測數目
totalNum=0;
for(int i=0;i<backup.length;i++) {
totalNum+=backup[i];
}
}
//下一個背包循環
for(int i= 0;i<predictEcs.size();i++) {
if(predictEcs.get(i).num!=0) {
flag=true;
break;
}
}

}
}
System.out.println("zai看Ecses");
for(int i=0;i<predictEcs.size();i++) {
System.out.println(predictEcs.get(i).name+" "+predictEcs.get(i).cpu+" "+predictEcs.get(i).eme+" "+predictEcs.get(i).num+" ");
}
}
/**返回結果是題目要求的字符串，格式是這樣的：
6
flavor5 3
flavor10 2
flavor15 1
（備注：如果某種虛擬機規格的預測結果為零，即對應寫0）
4
1 flavor5 2
2 flavor5 1 flavor10 1
3 flavor15 1
4 flavor10 1
* @return 返回兩階段的結果
*/
public String[] getResult() {
int listNum=1+predictEcs.size()+1+bagNum+1;
finalRes=new String[listNum];
//第一階段結果
finalRes[0]=""+totalNum;
for(int i=1;i<1+predictEcs.size();i++) {
finalRes[i]=predictEcs.get(i-1).name+" "+backup[i-1];
}
//第二階段結果
finalRes[predictEcs.size()+1]=" ";
finalRes[predictEcs.size()+2]=""+bagNum;
for(int i=predictEcs.size()+3;i<listNum;i++) {
int order=i-(predictEcs.size()+3)+1;
String aBag=secResult.get(order-1);
finalRes[i]=order+" "+aBag;
}
return finalRes;
}

}

作者：wenj17

郵箱：527132554@qq.com

?

轉載于:https://www.cnblogs.com/wenj17/p/9243237.html

總結

以上是生活随笔為你收集整理的2018年华为精英挑战赛初赛放置算法Java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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