问题描述:
给定n个物品和一个容量为capacity的背包,物品i的大小为w[i],物品i的价值为v[i]。如何选择物品装入背包,使背包中物品价值最大?
思路分析:动态规划
动态规划数组:dp[i][j]表示从前i个物品中挑选物品放入容量为j的背包中所得到的背包的总价值。
则面对第i个物品,有两种选择:放与不放。
①当目前背包容量大于等于当前物品的大小时,可以放,也可以不放,所以要选择两者的最大值。
不放:当前背包的价值和前一个状态(前i-1个物品)相等。所以,dp[i][j] = dp[i-1][j]。
放入:当前背包价值等于前(i-1)个物品判断之后再加上第i个物品的价值。所以,dp[i