emu in blogjava

用A*算法來擴展狀態樹，當問題稍微復雜一點的時候狀態樹生長的太厲害，沒有辦法在規定時間內找到解，失敗！

import java.util.*;

// 節點增長方式：
// 1、如果內存區域為空，讀取任一塊數據
// 2、如果內存區域非空，寫一個內存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {
String[]disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);
/*
disk = new String[] {"1 3 5 7","0 2 4 8","6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 7);
*/
System.out.println("All passed!");

}

private static int countRate = 100; //為了方便處理評分，把評分值放大一個倍數后取整。
private static int memorySector = 2; //內存可存放的數據
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
System.out.println(d);
if (d.countSecotrOrder() == countAim)
return d.operationCount / 2;
diskStatus.remove(d);
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -1);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String st = status.toString();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (st.endsWith(statusList.get(i).toString()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = (DiskStatus) list.get(0);
for (int i = 1, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
return result;
}

class DiskStatus {
// DiskStatus parentStatus;
// boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數記數
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
// parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉移一個塊到內存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統計最多的連續塊作為這個文件順序性的評估標準
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即排序完成。order=文件個數×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount*2;
}

// public int compareTo(Object o) {
// return ((DiskStatus) o).countSecotrOrder() - countSecotrOrder();
// }

public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('.');
result.append(file[j]);
}
result.append("(order:").append(countSecotrOrder()).append(")(count:").append(countStatus()).append(')').append(
'\n');
}
return result.toString();
}
}
}


  回復  更多評論
  

檢討了上面的A*算法，其中存在著兩個基本錯誤：
每擴展一個節點就把它從隊列中刪掉，造成下次構造出相同的狀態的時候沒有辦法知道。
用toString來判斷兩個狀態是否相同，但是toString里面除了基本的sector數據之外還有評分的數據，所以不同情況下生成的相同狀態會被判斷成不同狀態。

修正后的A*算法，可以計算出一個比較合理和可行的整理過程，但是沒有辦法保證找到最好的一種（擴展過多的可能性會造成運算超時）。

理論上說只要修改評估策略（countStatus函數）就可以保證算法總是朝正確的方向擴張，但是創造一個合理的評估函數本身就是一個難題。

也許A*算法根本就不是這道題的正解。




import java.util.*;

// 節點增長方式：
// 1、如果內存區域為空，讀取任一塊數據
// 2、如果內存區域非空，寫一個內存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {

String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);

disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 8);

System.out.println("All passed!");

}

private static int countRate = 1000; //為了方便處理評分，把評分值放大一個倍數后取整。
private static int memorySector = 2; //內存可存放的數據
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
// System.out.println(d);
if (d.countSecotrOrder() == countAim) {
int result = d.operationCount / 2;
System.out.print("-----------------------------------------\n" +
d);
while (d.parentStatus != null) {
d = d.parentStatus;
System.out.print("\n" + d);
}
return result;
}
d.expanded = true;
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -10);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String map = status.getDiskMap();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (map.equals(((DiskStatus) statusList.get(i)).getDiskMap()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = null;

for (int i = 0, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (!tmpStatus.expanded) {
if (result == null) {
result = tmpStatus;
} else {
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
}
}
return result;
}

class DiskStatus {
DiskStatus parentStatus;
boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數記數
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉移一個塊到內存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統計最多的連續塊作為這個文件順序性的評估標準
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即整理完成。order=文件個數×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount * 20;
}


public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('\t');
if (file[j] >= 0)
result.append(file[j]);
else
result.append('*');
}
result.append("\t\t");
}
result.append('\n');
// result.append("(order:").append(countSecotrOrder())
// .append(")(count:").append(countStatus())
// .append(")(operation:").append(operationCount).append(')')
// .append(
// '\n');
return result.toString();
}

private String diskMap = null;
private String getDiskMap() {
if (diskMap != null)
return diskMap;
StringBuffer map = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
map.append(file[j]).append(',');
}
map.append(';');
}
diskMap = map.toString();
return diskMap;
}
}
}
  回復  更多評論
  

public class DiskDefrag {

    public static void main(String[] args) {
        String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
        int size = 20;
        assertEquals(new DiskDefrag().minMoves(disk, size), 5);

        disk = new String[] {"0 1 2 3 5 4 6 7 8 9"};
        size = 10;
        assertEquals(new DiskDefrag().minMoves(disk, size), 2);

        disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
        size = 100;
        assertEquals(new DiskDefrag().minMoves(disk, size), 7);

        disk = new String[] {"31 32 30","27 28 29", "13 24 5",  "19 10 21", "12 3 34",
               "15 6 17", "18 9 0","16 7 8","11 22 23","20 1 2","4 25 26","33 14 35"};
        size = 38;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 17);

        disk = new String[] {"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20",
               "33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54",
               "58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55",
               "40 16 35 43 49 52 53 59", "37 14 50"};
        size = 60;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 50);
        System.out.println("All passed!");

    }

    private static void assertEquals(int a, int b) {
        if (a != b)
            throw new RuntimeException("assert failed!! Expected " + b +
                                       " but got " + a);
    }

    private int fileCount = 0;
    private int secCount, diskSize;
    private Object[] srcDiskElms;
    private int[][] destDiskElms;
    int maxSuperpositionCount = 0;
    public int minMoves(String[] disk, int size) {
        fileCount = disk.length;
        diskSize = size;
        // 整理String數據建立int數組
        srcDiskElms = getDiskElms(disk);
        // 計算全部文件占用的扇區數
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的編號
        //[1]==文件的起始位置
        //[2]==文件的最后一個扇區的位置+1
        //[3]==文件和原始狀態的重合區塊計數

        getMaxSuperpositionCount(0, 0, 0, 0);
        return secCount - maxSuperpositionCount;
    }

    private void getMaxSuperpositionCount(int n, int tmpSecCount,
                                          int tmpSuperpositionCount,
                                          int tmpMoveCount) {
        // 找重合程度最高的文件存儲方式
        if (n < fileCount) {
            for (int i = 0; i < fileCount; i++) {
                // 找到一個還沒有放進destDiskElms的文件（的編號）
                int k = 0;
                for (; k < n; k++)
                    if (destDiskElms[k][0] == i)
                        k = fileCount + 1;
                if (k < fileCount) {
                    int[] srcFile = (int[]) srcDiskElms[i];
                    destDiskElms[n][0] = i;
                    int fileSize = srcFile.length;
                    int lastFileEndOffset = (n == 0) ? 0 :
                                            destDiskElms[n - 1][2]; //上一個文件結束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超過這個位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一個扇區的位置+1
                        int superpositionCount = 0;
                        for (int j = 0; j < fileSize; j++)
                            if (srcFile[j] == fileOffset + j)
                                superpositionCount++;
                        int moveCount = fileSize - superpositionCount;
                        if (tmpMoveCount + moveCount<secCount - maxSuperpositionCount){
                            destDiskElms[n][3] = superpositionCount;
                            getMaxSuperpositionCount(n + 1,
                                    tmpSecCount + fileSize,
                                    tmpSuperpositionCount +
                                    superpositionCount,
                                    tmpMoveCount + moveCount);
                        }
                    }
                }
            }
        } else {
            int superpositionCount = 0;
            for (int i = 0; i < n; i++)
                superpositionCount += destDiskElms[i][3];
            if (maxSuperpositionCount < superpositionCount)
                maxSuperpositionCount = superpositionCount;

        }

    }

    private Object[] getDiskElms(String[] disk) {
        Object[] result = new Object[disk.length];
        for (int i = 0; i < disk.length; i++) {
            String[] d = disk[i].split(" ");
            int[] ar = new int[d.length];
            for (int j = 0; j < d.length; j++)
                ar[j] = Integer.parseInt(d[j], 10);
            result[i] = ar;
        }
        return result;
    }

}

  回復  更多評論
  

敗給這一組數據了：
{"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20","33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54","58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55","40 16 35 43 49 52 53 59", "37 14 50"}
期待結果：50
  回復  更多評論
  

簡單的蠻力搜索遞歸算法，很簡單，可以得出正確的結果，但是隨著問題空間的增長復雜度成指數增長，很恐怖。期待更有效率的解法，如果有好的算法給我一份: chuchuns@cn.ibm.com , 謝謝。

import java.util.Enumeration;
import java.util.Hashtable;

import junit.framework.TestCase;

public class DiskDefragmenter extends TestCase {

int min = Integer.MAX_VALUE;

public int minMove(int[][] files, int size) {
Disk _disk = new Disk();
int min = _doMove(_disk, files, size);
return min;
}

int _doMove(Disk disk, int[][] files, int size) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < files.length; i++) {// 找到第一個可以放的
if (disk.containsFile(i))
continue;

for (int j = 0; j < size; j++) {
int moveCount = 0;

if (!disk.canPut(j, j + files[i].length -1))
continue;
if (files[i].length + j > size - 1)
break;

System.out.println("" + (i+1) + ": " + j + "-" + (j + files[i].length -1));

Disk tempDisk = new Disk(disk);
BigSeg one = new BigSeg();
one.low = j;
one.high = j + files[i].length - 1;
tempDisk.insertSeg(i, one);

moveCount += calculateMoveCount(files[i], j);

int t = _doMove(tempDisk, files, size);

moveCount += t;
if (min > moveCount) {
min = moveCount;
}

}

}
if (disk.size() == files.length)
return 0;
return min;

}

int calculateMoveCount(int[] seg, int index) {
int count = 0;
int _index = index;
for (int i = 0; i < seg.length; i++, _index++) {
if (seg[i] != _index)
++count;
}
return count;
}

public static void main(String args[]) {
}

class BigSeg implements Cloneable {
int low, high;

public BigSeg(){}
public BigSeg(BigSeg b) {
low = b.low;
high = b.high;
}
}

class Disk {
/**
* i:BigSeg
*/
Hashtable ht = new Hashtable();

public Disk(){
//
}

public Disk(Disk d) {
Enumeration e = d.ht.keys();
while (e.hasMoreElements()) {
int k = ((Integer) e.nextElement()).intValue();
BigSeg b = new BigSeg((BigSeg) d.ht.get(new Integer(k)));
ht.put(new Integer(k), b);

}

}

public int size() {
return ht.size();
}

boolean contains(int low, int high) {
Enumeration em = ht.elements();
while (em.hasMoreElements()) {
BigSeg e = (BigSeg) em.nextElement();
if ((low <= e.high && low >= e.low)
| (high <= e.high && high >= e.low))
return true;
}

return false;
}

public void insertSeg(int i, BigSeg one) {
ht.put(new Integer(i), one);

}

boolean canPut(int low, int high) {
return !contains(low, high);
}

public boolean containsFile(int i) {
return ht.containsKey(new Integer(i));
}
}

}
  回復  更多評論
  

呵呵，你跟我前面兩次解此題走的是同樣的方向，其實都忽略了一點：題目要求的是最少移動的次數，不是具體的移動方案。
失敗兩次后我開始認為，具體的移動方案可能性增長太快，不要說盲目搜索，就是很優化的搜索策略也經不住增長。其實我們需要的是找到一個通用的算法可以直接推算出來需要移動的最少次數，并且從數學上保證這個次數的方案的存在。我第三次的嘗試走的就是這個方向，可惜也沒有成功。
如果求具體的移動的方案，這也不失為一道非常好的練習題。盲目搜索沒有多大意義的，我已經試過A*了，另外有朋友說他也試過遺傳算法，你有什么其他的想法也不妨再試試看。
  回復  更多評論
  

bitterlemon(春生)的方案是不是有點問題？

用{"1 3 5 7", "0 2 4 8", "6 9"}, 100這組數據測，居然有8千多組解(minimum sectors = 7)

而且同樣這組數據、即使磁盤容量為10，也可以通過移動7塊得到結果，可是這個程序得到的解為-2147483645  回復  更多評論
  

BitMask/DP  回復  更多評論
  

用動態規劃？具體怎么做呢？
cheapwine是judgeonline過來的啊？
  回復  更多評論
  

2^12種狀態，硬做。  回復  更多評論
  

能做到2^12種狀態就好了。我分析的結果是12！種狀態阿，比2^12多了十萬倍以上。  回復  更多評論
  

@emu

設當前 狀態 為 [-1,-1] [-1,-1] a1 a2 a3 ... an [-1,-1] ... [-1,-1] b1 b2 .. bk [-1,-1] [-1,-1]
[x,y] 表示第x個文件的第y塊

如{"3 4 5 6 8 9 10","17 16 15"} 20
轉變為 [-1 -1] [-1 -1] [-1 -1] [0 0] [0 1] [0 2] [0 3] [-1 -1] [0 4] [0 5] [0 6] [-1 -1] [-1 -1] [-1 -1] [-1 -1] [1 2] [1 1] [1 0] [-1 -1] [-1 -1]

{"1 3 5 7","0 2 4 8","6 9"} 100
轉變為 [1 0] [0 0] [1 1] [0 1] [1 2] [0 2] [2 0] [0 3] [1 3] [2 1] [-1 -1] [-1 -1] 。。。。

設S[i] 為當前的移動次數

有兩種方法到達下一狀態
1。[-1 -1] 和 一非[-1 -1]交換
2。兩非[-1 -1]交換 （借助2個cache）

則S[i+1] = min ( 方法1+1，方法2+2 )

由于最后還需要順序性和連續性，交換的時候必須保證 如[p q+1]必須和[p q]之后的塊交換。   回復  更多評論
  

注意到，下一狀態并不是唯一的，對于已知的S[i]，所有的S[i+1]中的最小值也不一定就是我們到達S[n]的一個必經之途，關鍵問題不在于對一個已知的S[i]和S[i+1]怎么取得最小操作次數，而在于，在若干個S[i+1]狀態中那個能讓我們的S[n]得到最小值呢？  回復  更多評論
  

hgw的解答：
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int z[100+8][1<<12];
class DiskDefrag
{
public:
static int minMoves(vector<string> disk, int size)
{
int n,i,j,k,now,lx[12][64],my[12],get[12][100+8];
n=disk.size();
for(i=0;i<n;i++) //讀入數據
{
my[i]=0; //my[i]表示第i個文件的長度
now=-1;
for(j=0;j<disk[i].size();j++)
if(disk[i][j]>='0'&&disk[i][j]<='9')
{
if(now==-1)
now=disk[i][j]-'0';
else
now=now*10+disk[i][j]-'0';
}
else if(now!=-1)
{
lx[i][my[i]++]=now;
now=-1;
}
if(now!=-1)
lx[i][my[i]++]=now;
}
memset(get,0X10,sizeof(get));
//get[i][j]表示第i個文件的最后一個扇區存放在j的移動步數
for(i=0;i<n;i++)
for(j=0;j<size;j++)
if(j+1>=my[i])
{
get[i][j]=0;
for(k=0;k<my[i];k++)
if(lx[i][my[i]-k-1]!=j-k)
get[i][j]++;
}
memset(z,0X10,sizeof(z));
/*
z[i][j]表示到第i個扇區，n個文件的二進制狀態為j(1表示該文件已搞定，0表示未)的最小步數
z[i][j]=min{[i-1][j],[i-my[k]][j^(1<<k)]+get[k][i](k=0,1,2,……,n-1且(i&(1<<k))>0)}
*/
for(i=0;i<size;i++)
for(j=0;j<(1<<n);j++)
{
if(i&&z[i-1][j]<z[i][j])
z[i][j]=z[i-1][j];
for(k=0;k<n;k++)
if(j&(1<<k))
{
if(i+1>=my[k])
{
if(i-my[k]<0) //[-1][0]=0的實現
{
if(!(j^(1<<k)))
if(get[k][i]<z[i][j])
z[i][j]=get[k][i];
}
else
{
if(z[i-my[k]][j^(1<<k)]+get[k][i]<z[i][j])
z[i][j]=z[i-my[k]][j^(1<<k)]+get[k][i];
}
}
}
}
return z[size-1][(1<<n)-1];
}
};
int main() //測試數據，你blog上的那一組，期望結果：50
{
vector<string> a;
int b;
a.push_back("8 0 7 51");
a.push_back("47 22 26 30 46");
a.push_back("41 4 9 10 20");
a.push_back("33 5 28 39 42");
a.push_back("31 12 56 57");
a.push_back("13 6 17 24 27 36 54");
a.push_back("58 32 34 45");
a.push_back("19 2");
a.push_back("3 11 15 25 38 48");
a.push_back("23 1 18 21 29 44 55");
a.push_back("40 16 35 43 49 52 53 59");
a.push_back("37 14 50");
b=60;
printf("%d\n",DiskDefrag::minMoves(a,b));
return 0;
}  回復  更多評論
  

wqb的解答
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<memory>
#include<math.h>
#include<time.h>
#include<string.h>
#include<algorithm>

using namespace std;

#define minx(i,j) ((i)<(j)?(i):(j))
#define maxx(i,j) ((i)>(j)?(i):(j))
#define abxx(i) ((i)>0?(i):(-(i)))
#define eps 1e-9
#define mod (1<<20)

int dp[128][1<<12];
int ro[128][1<<12];
int pr[128][1<<12];
int ll[128][1<<12];
int ax[128][1<<12];

inline bool digit(char i)
{
return i>='0'&&i<='9';
}

class DiskDefrag
{
public:
void dfsoutlujing(int s,int i)
{
if(!i)return ;
while(pr[s][i]!=s)s=pr[s][i];
dfsoutlujing(ll[s][i],i^(1<<(ro[s][i])));
printf("在 %d %d 區間 放 %d 的塊 需要移動的步數 %d\n",s-ll[s][i],s,ro[s][i],ax[s][i]);
}
int minMoves(vector<string> disk, int size)
{
int s=disk.size();

int len[16];

int sector[16][128];

int i;
int j;
int k;
int t;
int x;

for(i=0;i<s;i++)
{
k=-1;len[i]=0;
for(j=0;disk[i][j];j++)
{
if(digit((char)(disk[i][j])))
{
if(k==-1)k=disk[i][j]-'0';
else k=k*10+disk[i][j]-'0';
}
else if(k!=-1)
{
sector[i][len[i]++]=k;
k=-1;
}
}
if(k!=-1)
sector[i][len[i]++]=k;
}

int sum=0;

for(i=0;i<s;i++)
sum+=len[i];

if(sum>size)return -1; // 不能移動

//////////////////////////////

memset(dp,1,sizeof(dp));

for(i=0;i<128;i++)
dp[i][0]=0;

for(j=0;j<size;j++)
for(i=1;i<(1<<s);i++)
{
t=-1;
for(k=0;k<s;k++)
if(i&(1<<k))
t+=len[k];
if(t>j)
continue;

if(j)
{
dp[j][i]=dp[j-1][i];
pr[j][i]=j-1;
}

for(k=0;k<s;k++)
if(i&(1<<k))
{
t=0; // cost
for(x=0;x<len[k];x++)
if(sector[k][x]!=x+j-len[k]+1)
t++;

if(dp[j-len[k]][i^(1<<k)]+t<dp[j][i]) // 最優子結構
{
dp[j][i]=dp[j-len[k]][i^(1<<k)]+t;
ro[j][i]=k;
pr[j][i]=j;
ax[j][i]=t;
ll[j][i]=j-len[k];
}
}
}

dfsoutlujing(size-1,(1<<s)-1); // 打印路徑

if(sum==size&&dp[size-1][(1<<s)-1])
return -1;
else
return dp[size-1][(1<<s)-1];
}
};

int main()
{
int i;

DiskDefrag wqb;

while(scanf("%d",&i)==1)
{
double wqbdf=clock();

int ncase;
vector<string> df;
scanf("%d",&ncase);
for(i=0;i<ncase;i++)
{
int s;
string smy;
bool flag=false;
char str[16];
scanf("%d",&s);
for(int j=0;j<s;j++)
{
if(flag)smy+=' ';
else flag=true;

scanf("%s",str);

for(int k=0;str[k];k++)
smy+=str[k];
}
df.push_back (smy);
}
scanf("%d",&i);
printf("%d\n",wqb.minMoves (df,i));

printf("%lf\n",clock()-wqbdf);
}

return 0;
}






/*

1
2
7
3 4 5 6 8 9 10
3
17 16 15
20
1
1
8
1 2 3 5 4 6 7 8
10
1
3
4
1 3 5 7
4
0 2 4 8
2
6 9
100

1
12
4
8 0 7 51
5
47 22 26 30 46
5
41 4 9 10 20
5
33 5 28 39 42
4
31 12 56 57
7
13 6 17 24 27 36 54
4
58 32 34 45
2
19 2
6
3 11 15 25 38 48
7
23 1 18 21 29 44 55
8
40 16 35 43 49 52 53 59
3
37 14 50
89

1
1
2
0 1
2

*/  回復  更多評論
  

學習了,有點用處,  回復  更多評論