文件名称：“背包问题”递归调用的PPT详解
文件大小：6.02MB
文件格式：PPTX
更新时间：2022-03-22 11:52:05
递归调用的PPT详解
令a[]为各个物品的重量，m为背包容量，n表示第n个物品 。从后往前看， 1.如果当前没有物品，直接返回false。 2.如果当前背包的容量恰为第n个物品的重量，返回true 。 3.如果当第n个物品的重量大于当前背包容量 ，①当前物品为第一个物品，那么肯定找不到，返回false；②当前不是第一个物品，那么就在前n-1个物品中继续找，返回pack（a,n-1,m）。 4.当第n个物品的重量小于当前背包容量，①让背包装下此物品，那么调用pack（a,n-1,m-a[n]）;②不让背包装下此物品，那么调用pack（a,n-1,n）；二者如有一中情况满足，那么此问题就有解。