问：
任意给定十种物品，物品i的重量是Wi，其价值为Vi，给定一个载重量为Capacity的口袋
答：
这个问题属于0-1背包问题,是计算机算法中的一个经典问题。
问题描述:有N种物品,第i种物品的重量为Wi,价值为Vi,和一个载重量为Capacity的背包。怎么选择物品放入背包,使得背包中物品的总价值最大?
这个问题可以用动态规划解决:
1. 定义状态:dp[i][j]表示前i个物品放入一个载重量为j的背包可以得到的最大价值。
2. 递推公式:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-Wi] + Vi)
意思是,对于第i个物品,有两种选择:
(1) 不把第i个物品放入背包,总价值保持不变,等于dp[i-1][j]
(2) 把第i个物品放入背包,那么总价值等于不放第i个物品时的总价值dp[i-1][j-Wi]加上第i个物品的价值Vi
取两种选择的最大值,就是dp[i][j]
3. 初始化:dp[0][j] = 0,表示如果没有物品,价值为0
4. 结果:dp[N][Capacity]就是最大总价值
5. 时间复杂度:O(N*Capacity),空间复杂度O(N*Capacity)
举例:有3种物品,重量和价值分别是(1, 3),(2, 4),(3, 5),背包容量为5
则dp数组为:
0 0 0 0 0
0 3 3 3 3
0 3 4 6 6
0 3 4 6 7
0 3 4 6 7
所以最大总价值为7。
这就是0-1背包问题的动态规划解法,希望解释详尽!