动态规划之01背包问题

微信公众号：程序员风离

个人博客 ： 点我

CSDN: 点我

欢迎━(｀∀´)ノ亻!关注公众号

---

动态规划之01背包问题

问题引出：

​ 一个背包最大容量为8 现有4个物品 每个物品各自有不同的容量和不同的价值 求在不超过背包最大容量的情况下最大物品价值

如图所示

物品编号	物品所需容量(weight)	物品价值（value）
1	2	6
2	3	10
3	4	12
4	5	15

设 f(k,w) k为背包最大存入物品数量 w 为背包最大容量

每一次存放物品都有两种情况

• weight>8 (太重放不下)
  • 放不下就向下走 k-1 w因为没存放物品 保持不变 f(k,w) =f(k-1,w)
• weight<=8 (能放下 然后选择是否存放 这里也有两种情况 )
  • 如果选择放下 f(k,w) = f(k-1,w-weight) + (weight,value) weight对应的value
  • 如果选择不放下 f(k,w) = f(k-1,w) 继续向下走 例如当前是第三号物品 存放不下 就向下找 三号物品是否能放下 （放不下 value为0）

状态转移方程为：

由上述方程可列出图表

背包容量	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1： w =2 v=6	0	0	6	6	6	6	6	6	6
2: w=3 v=10	0	0	6	10	10	16	16	16	16
3: w=4 v=12	0	0	6	10	12	16	18	22	22
4: w=5 v=15	0	0	6	10	12	16	18	22	25

由上述方程可代码实现（Java）

/**
 * Created with IntelliJ IDEA.
 *
 * @author: 风离
 * @Date: 2021/11/27/14:30
 * @Description:
 */
public class Test {
    public static void main(String[] args) {
        int[][] f =new int[5][9]; // f[i][j]表示前i件物品，背包容量为j的最大价值
        int[]w=new int[]{0,2,3,4,5}; //重量
        int[]v=new int[]{0,6,10,12,15}; //价值

        for(int i=1;i<5;i++)
        {
            for(int j=1;j<9;j++)
            {
                if(w[i]>j)
                {
                    f[i][j]=f[i-1][j];
                }else {
                    f[i][j]=Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
                }
            }
        }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(f[i][j]+" ");
            }
            System.out.println();
        }


    }
}

运行截图：

符合图表所示