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

*/  回复  更多评论
  

学习了,有点用处,  回复  更多评论