01背包问题

01背包问题

问题描述

一个旅行者有一个最多能装m公斤的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？

思路

　假设前n个物品，总承重为j，物品的重量为w，其最大价值为v[n,j]。

　在背包的总承重不变的前提下，一个物品是否放入背包中直接影响到后面的物品是否能放入到背包中，即一个物品很重同事物品价值又很低时，若装入背包中直接导致其他更多的物品无法放入背包中，从而使得背包中的最大总价值变低。

　　当背包的承重为0，或者不将物品放入背包时，背包中的最大总价值均为0，即v[n,0]=v[0,n]=0。

　　放入当前物品n超过背包的最大承重时，则无法将该物品放入背包中，即v[n,j]=v[n-1,j]。　

放入当前物品n不超过背包的最大承重时，则当前物品放入背包时的最大价值为vn+v[n-1,j-wn]，不放入背包时的最大价值为v[n-1,j]，因此对于当前物品是否放入背包中所能获得的最大价值为v[n,j]=max{ v[n-1,j],vn+v[n-1,j-wn] }。

状态转化方程为：

public static int[][] dp_bag(int m,int n,int w[],int p[]){

    int[][] c=new int[n+1][m+1];

    for(int i=0;i<n+1;i++) {

        c[i][0]=0;

    }

    for(int j=0;j<m+1;j++) {

        c[0][j]=0;

    }

    for(int i=1;i<n+1;i++) {

        for(int j=1;j<m+1;j++) {

            //当物品为i件重量为j时，如果第i件的重量（w[i-1])小于重量j时，c[i][j]为下列两种情况之一：

            //(1)物品i不放入背包中，所以c[i][j]为c[i-1][j]

            //(2)物品i放入背包中，则背包剩余重量为j-w[i-1,所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值

            if(w[i-1]<=j) {

                if(c[i-1][j]<c[i-1][j-w[i-1]]+p[i-1]) {

                    c[i][j]=c[i-1][j-w[i-1]]+p[i-1];

                }else {

                    c[i][j]=c[i-1][j];

                }

            }else {

                c[i][j]=c[i-1][j];

            }

        }

    }

    return c;

}