写在最前面， 这些方法肯定不是我原创的，也是看的别人的思路，
然后自己理解并且实现了
https://blog.csdn.net/iihtd/article/details/51611810?utm_source=blogxgwz2
这个里面讲了背包问题，以及背包的衍生问题，还是不错的，
https://blog.csdn.net/stack_queue/article/details/53544109
这个是著名的背包九讲，讲的很好
0-1 背包问题：
0-1 背包问题解决的是物品只能够选择1次要不就不选，在背包能够装得下的前提下面，能够保证装的价值最大：
状态转移方程 f[i][j] = max{ f[i-1][j] , f[i-1][j - wi] +vi }; 0≤j - wi≤j
用二维的空间来表示是比较简单的
一维表示：f[v] 表示 f[i][v] , 那么由于上面的这个公式： f[i][j] = max{ f[i-1][j] , f[i-1][j - wi] +vi };
可以发现f[i][j] 的值只是和f[j-1][j] , 和f[i-1][j-wi] ，如果我们写出如下的代码：
for(int i = 0 ; i < n ; i++){
for(int j = m ; j >=0 ; j--){
vec[j] = max(vec[j] , vec[j-w[i]]+v[i] );
}
}
那么对于i = N 的情况，我们计算 vec [j] 时， 由于j-wi < j ,那么vec[j-w[i]]的值会在vec[j]后参与计算，所以，在计算vec[j ] 的时候，我们先读取到的vec[j] 实际上是vec[N-1][j] , 读取到的 vec[j-w[i]]实际上是vec[N-1][j-w[i]]，所以可以用上面的公式进行简化。
现在是0-1背包问题的二维代码实现：
/**
int[] w 表示物品的重量数组
int[] v 表示物品的价值
int weight 表示背包能够装入的重量
*/
public static int backpack01(int[] w, int[] v, int weight) {
int n = w.length + 1; //多少个物品
int[][] temp = new int[n][weight + 1];
for (int i = 0; i < n; i++) {
temp[i][0] = 0;//代表背包承受0重量时，背包的价值
}
for (int j = 0; j < weight + 1; j++) {
temp[0][j] = 0;//代表背包存放0个物品时，背包的价值
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < weight + 1; j++) {
if (j > w[i]) { //这样背包才能放下这个物品
temp[i][j] = Math.max(temp[i - 1][j], temp[i - 1][j - w[i]] + v[i]);
} else {
temp[i][j] = temp[i - 1][j];
}
}
}
return temp[n-1][weight];
}
现在是0-1背包问题的一维代码实现
当只有第一个物品的时候，相当于是往背包里面装第一个东西，
第二遍是有两个物品的时候了，相当于在有第一个物品的基础上，
放第二个物品来使背包价值最大化
/**
int[] w 表示物品的重量数组
int[] v 表示物品的价值
int weight 表示背包能够装入的重量
*/
public static int backpack01youhua(int[] w, int[] v, int weight) {
int[] f = new int[weight + 1];
for (int i = 0; i < v.length; i++) {
for (int j = weight; j >= w[i]; j--) {
f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
}
}
return f[weight];
}
完全背包问题
完全背包问题中每个物品都可以选择无限多次
for (int j = 0; j <=weight; j++)
所以这个地方不同于01背包从背包里面扔东西，
这个是往背包里面一步一步的加
/**
int[] w 表示物品的重量数组
int[] v 表示物品的价值
int weight 表示背包能够装入的重量
*/
public static int completebackpack(int[] w, int[] v, int weight) {
int[] f = new int[weight + 1];
for (int i = 0; i < v.length; i++) {
for (int j = 0; j <=weight; j++) {
f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
}
}
return f[weight];
}
多重背包问题
部分物品的数量有限，那就和01背包问题一样
/**
int[] w 表示物品的重量数组
int[] v 表示物品的价值
int[] num 表示每个物品的数量
int weight 表示背包能够装入的重量
*/
public static int completebackpack(int[] w, int[] v, int[] num, int weight) {
int[] f = new int[weight + 1];
for (int i = 0; i < v.length; i++) {
for (int j = weight; j >= w[i]; j--) {
for (int k = 1; k <= num[i]; k++) {
if (j - k * w[i] > 0 && f[j - k * w[i]] + k * w[i] > f[j]) {
f[j] = f[j - k * w[i]] + k * w[i];
}
}
}
}
return f[weight];
}
背包衍生问题: 硬币凑整数 即子集合加总问题
硬币问题和完全背包问题类似，原题是这样的：有1分,2分,5分,10分四种硬币,每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱?
采用动态规划的思路,f(i,j)表示的是可以取的0,1,2...i种硬币的情况下,凑够j元一共有多少种方法.递推公式以及相应的一维如何推导为二维如下:
image.png
/**
int[] coins 代表有多少种类型的coin
int target 代表要凑成的数目
*/
public static int coins(int[] coins, int target) {
int n = coins.length;
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= target; j++) {
f[j] = f[j] + f[j - coins[i]];
}
}
return f[target];
}
附加一个衍生问题
https://www.cnblogs.com/wudongyang/p/4949557.html
0-1背包问题与子集合加总问题的近似算法
组合总和IIIhttps://blog.csdn.net/wjoker/article/details/84404478
输入两个整数值n和m，求出整数1到n之间的和为m的所有组合
https://blog.csdn.net/qq_36653505/article/details/82634774 python版本简单， java版本麻烦一些
https://blog.csdn.net/weixin_37365120/article/details/70068214
给定一个数组，从中查找是否存在两个数的和等于一个给定的x
另外借鉴了人家一种o(n)的方法，借用一个容器，在容器中查找x-arr[n]的值是否存在，存在就返回 true，不存在将这个值加入容器。
https://blog.csdn.net/chen3749102/article/details/45336371
public static boolean hasAB(int[] arr, int x){
HashSet<Integer> set=new HashSet<>();
for(int i=0;i<arr.length;i++){
if(set.contains(x-arr[i]))
return true;
else
set.add(arr[i]);
}
return false;
网友评论