背包问题

题目链接

题目描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值. 问最多能装入背包的总价值是多大?

解题思路

代码实现

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 num = A.length; if(m == 0 || num == 0) return 0; //多加一行一列，用于设置初始条件 int[][] maxValue = new int[num + 1][m + 1]; //初始化所有位置为0，第一行和第一列都为0，初始条件 for(int i = 0; i <= num; ++i){ maxValue[i][0] = 0; } for(int i = 1; i <= m; ++i){ maxValue[0][i] = 0; } for(int i = 1; i <= num; ++i){ for(int j = 1; j <= m; ++j){ //第i个商品在A中对应的索引为i-1: i从1开始 //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同 if(A[i - 1] > j){ maxValue[i][j] = maxValue[i - 1][j]; } else{ //如果可以装下，分两种情况，装或者不装 //如果不装，则即为(i-1, j) //如果装，需要腾出放第i个物品大小的空间： j - A[i-1],装入之后的最大价值即为(i -1, j - A[i-1]) + 第i个商品的价值V[i - 1] //最后在装与不装中选出最大的价值 int newValue = maxValue[i - 1][j - A[i - 1]]+ V[i - 1]; maxValue[i][j] = Math.max(newValue, maxValue[i - 1][j]); } } } //返回装入前N个商品，物品大小为m的最大价值 return maxValue[num][m]; } }

优化算法

上面的算法在计算第i行元素时，只用到第i-1行的元素，所以二维的空间可以优化为一维空间，但是如果是一维向量，需要从后向前计算，因为后面的元素更新需要依靠前面的元素未更新（模拟二维矩阵的上一行的值）的值

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 num = A.length; if(m == 0 || num == 0) return 0; //多加一列，用于设置初始条件，因为第一件商品要用到前面的初始值 int[] maxValue = new int[m + 1]; //初始化所有位置为0，第一行都为0，初始条件 for(int i = 0; i <= m; ++i){ maxValue[i] = 0; } for(int i = 1; i <= num; ++i){ for(int j = m; j > 0; --j){ //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同 //如果可以装下，分两种情况，装或者不装 //如果不装，则即为(i-1, j) //如果装，需要腾出放第i个物品大小的空间： j - A[i],装入之后的最大价值即为(i - 1, j - A[i-1]) + 第i个商品的价值V[i] //最后在装与不装中选出最大的价值 if(A[i - 1] <= j){ int newValue = maxValue[j - A[i - 1]] + V[i - 1]; maxValue[j] = Math.max(newValue, maxValue[j]); } } } //返回装入前N个商品，物品大小为m的最大价值 return maxValue[m]; } }