分类:01背包 完全背包
01: 多个物品,每个只有一个,物品有 weight 和value。背包载重有限制,问最多能放多少;
完全:多个物体,每个有无数个
dp[i][j] 的含义:在【0,i】这么多物品中,放入载重为 j 的背包内的最大价值。
物品/载重 | 载重0 | 载重1 | 载重2 | 载重3 |
物品0 | ||||
物品1 | ||||
物品2 | ||||
物品3 |
递推式:dp[ i ] [ j ]= max( dp[ i-1 ] [ j -weight [ i ] ] + value[ i ] , dp[ i-1 ] [ j ] ) ----- 只与目标格的正上方以及左上方有关,所以初始化第一行和第一列, 其他的可以初始化为0;
初始化:只用初始化第一行,方法for (weight小于bagweight 则初始化为value)其他的初始化为多少都行,为方便初始化为0;
表格内填的是value;