最优装载—dp

最优装载—dp

动态规划

一 问题描述
最优装载—dp

二 问题分析
最优装载—dp

三 代码实现

package dp_Loading;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException; public class bin
{
public static void main(String[] args) throws IOException
{
int []w={0,20,10,40,30,50,60,70};
int c=180;
dp_Loading myDp_Loading=new dp_Loading(w, c);
}
}
class dp_Loading
{
int w[];
int c;
int cc;
int m[][];
int x[]; //迭代路线记录
public dp_Loading(int w[], int c) throws IOException
{
this.c=c;
this.cc=c;
this.w=w;
this.m=new int [w.length][c+1];
this.x=new int [w.length];
Dp_Loading();
display();
}
public void Dp_Loading()
{
for(int i=0; i<w.length; i++)
{
m[i][0]=0; //船的容量为0
}
for(int j=0; j<=c; j++)
{
m[0][j]=0; //没有集装箱可装
}
for(int i=1; i<w.length; i++)
{
for(int j=1; j<w[i]; j++)
{
m[i][j]=m[i-1][j];
}
for(int j=w[i]; j<=c;j++)
{
m[i][j]=Math.max(m[i-1][j], m[i-1][j-w[i]]+w[i]);
}
}
//恢复迭代路径
for(int i=w.length-1; i>=1; i--)
{
if(m[i][cc]==m[i-1][cc]) //这个集装箱没有装入
{
x[i]=0;
}
else
{
x[i]=1;
cc-=w[i];
}
}
}
public void display() throws IOException
{
BufferedWriter fout=new BufferedWriter(new FileWriter("out.txt"));
fout.write("c="+c);
fout.newLine();
fout.write("optw="+m[w.length-1][c]);
fout.newLine();
fout.write("m[i][j]:");
fout.newLine();
for(int i=0; i<w.length; i++)
{
for(int j=0; j<=c; j++)
{
fout.write("\t"+m[i][j]);
}
fout.newLine();
}
fout.write("x[i]:");
fout.newLine();
for(int i=1; i<w.length; i++)
{
fout.write("\t"+x[i]);
fout.newLine();
}
fout.flush();
}
}

四 运行结果
最优装载—dp

五 总结收获

  1. dp 关键在于得到递归方程
  2. 由递归方程分析迭代过程,最后给出循环

六不足

  1. dp应当多加练习
上一篇:HDU 1213 How Many Tables(模板——并查集)


下一篇:js-dot.js