动态规划 背包问题

本篇博文参考此博文，该博文PPT非常有助理解

问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-1背包问题。
过程分析
数据：
物品个数n=5
物品重量w[n]={0，2，2，6，5，4}
物品价值V[n]={0，6，3，5，4，6}
总重量c=10
（第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理。）
背包的最大容量为10，那么在设置数组m大小时，可以设行列值为6和11，那么，对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。

感觉动态规划问题的核心还是在于在已有解决方案的基础上优化，背包问题两点是构建二维数组和通过数组寻找最优解。
构建的核心在于比较寻找最大值。如下图所示，核心就是理解Max的寻找过程

还原最优解的时候呢，则是根据构造思路的一个逆向思考。

ppt均来源与顶部博文

public class test03232137 {
    
    public static int m[][]=new int[6][11];  
    public static int c=10;//背包容量
    public static int[] w={0,2,2,6,5,4};//物品重量
    public static int[] v={0,6,3,5,4,6};//物品对应的价值
    public static int n=5;//n为物品的个数
    public static int[] x=new int[n+1];
    public void package_1(int m[][],int w[],int v[],int n)//n代表物品的个数 
    {  
        //采用从底到顶的顺序来设置m[i][j]的值  
        //首先放w[n]  
        for(int j = 0; j <= c; j++)  
           if(j < w[n]) m[n][j] = 0;     //j小于w[n],所对应的值设为0，否则就为可以放置   
           else         m[n][j] = v[n];  
             
        //对剩下的n-1个物品进行放置。  
        int i;  
        for(i = n-1; i >= 1; i--)  
            for(int j = 0; j <= c; j++)  
               if(j < w[i])   
                            m[i][j] = m[i+1][j];//如果j < w[i]则，当前位置就不能放置，它等于上一个位置的值。  
                                                //否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中较大者。              
               else         m[i][j] = m[i+1][j] > m[i+1][j-w[i]] + v[i]?   
                                      m[i+1][j] : m[i+1][j-w[i]] + v[i];    
    }  
    
    public void answer(int m[][],int n)  
    {  
        int j = c;  
        int i;  
        for(i = 1; i <= n-1; i++)  
            if(m[i][j] == m[i+1][j])
                x[i] = 0;  
            else{
                x[i] = 1;  
                j = j - w[i];  
            }      
        x[n] = (m[i][j]==m[i-1][j]) ? 1 : 0;   
    }
    public static void main(String[] args){
        test03232137 t=new test03232137();
        
        t.package_1(m,w,v,n);  
         for(int i = 0; i <= 5; i++)  
         {  
             for(int j = 0; j <= 10; j++)  
             System.out.print(" "+m[i][j]+" ");
             System.out.println();
         }   
         t.answer(m,n);  
         System.out.print("The best answer is:");  
         for(int i = 1; i <= 5; i++)  
             System.out.print(" "+x[i]+" "); 
    }
    
}

运行结果如图