01背包问题刷题总结：
125.?背包问题 II
中文
English
有?n?个物品和一个大小为?m?的背包. 给定数组?A?表示每个物品的大小和数组?V?表示每个物品的价值.
问最多能装入背包的总价值是多大?
Example
样例 1:
输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
样例 2:
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int n = A.length;
int[]f = new int[m+1];
int i,w;
for(i=1;i<=m;++i) {
f[i] = -1;
}
for(i=1;i<=n;++i) {
//f[0] f[1]
for(w=m;w>=0;--w) {
if(w>=A[i-1]&& f[w-A[i-1]]!=-1 ) {
f[w] = Math.max(f[w],f[w-A[i-1]]+V[i-1] );
}
}
}
int res = 0;
for (i=0;i<=m;++i) {
if(f[i]!=-1) {
res = Math.max(res,f[i]);
}
}
return res;
?
}
}
?
思路总结：
把数组压成一行，一定要倒着求
?
?
?
总结 backPack d方程：
dp[i][w] = max( dp[i-1][w], dp[i-1][ w-A(i-1)] + V(i-1) )
?
其中：
dp[i][w] 表示用前 i 个物品拼出重量w时最大总价值。
dp[i-1][w] 表示 用 前 i-1 个物品拼出重量 w时最大总价值
最后一个是 用前 i-1 个物品拼出总重量 w -A(i-1) 时 最大总价值，加上第 i个物品。
?
?
Backpack 可行性
--题面： 要求不超过 Target时能拼出的最大重量
--记录 f[i][w] = 前 i个物品能不能拼出 重量 w
backpack V, backpack VI , 计数型背包
--题面： 要求有多少种方式拼出重量 Target
-- 记录 f[i][w] = 前 i个物品有多少种方式拼出 重量 w
backpack II, backpack iii , 最值型
-- 题面： 记录能拼出的最大价值
-- 记录f[i][w] = 前 i 个/种物品拼出重量 w能得到的最大价值
?
?
关键点：
-最后一步：
1. 最后一个背包内物品是哪个
2. 最后一个物品有没有背包
-数组大小和最大承重 Target有关
?
?
?
?
?
?
?
?
?
?
?
原文：https://www.cnblogs.com/lyr-2000/p/13060521.html