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();

    }

}