在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
样例
如果有4个物品[2, 3, 5, 7]
如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。
如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。
函数需要返回最多能装满的空间大小。
解题
动态规划
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][j]前i个物品放入大小为j的空间里能够占用的最大体积。
则其状态转移方程便是：
f[i][j]=max{f[i-1][j],f[i-1][j-A[i]]+A[i]}
不放第i个物品：f[i-1][j]
放第i个物品：那么问题就转化为“前i-1件物品放入剩下的容量为j-A[i]的背包中”，此时能获得的最大体积就是f[i-1][j-A[i]]再加上通过放入第i件物品获得的体积A[i]
注意上面的状态转移方程i的下标是从1开始的，下面程序是从0开始的，要适当调整
public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { // write your code here int[][] P = new int[A.length+1][m+1]; for(int i = 1;i<= A.length; i++){ for(int j = m;j>=0;j--){ if(j>=A[i-1]){ P[i][j] = P[i-1][j-A[i-1]] + A[i-1]; } P[i][j] = Math.max(P[i][j],P[i-1][j]); } } return P[A.length][m]; } }
或者对0的时候单独考虑
public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { // write your code here int[][] P = new int[A.length][m+1]; for(int i = 0;i< A.length; i++){ for(int j = m;j>=0;j--){ if(i==0){ // 第0个物品可以放入空间为j的背包中，直接放入 if(j>=A[i]) P[i][j] = P[i][j-A[i]] + A[i]; }else{ if(j>=A[i]){ P[i][j] = P[i-1][j-A[i]] + A[i]; } P[i][j] = Math.max(P[i][j],P[i-1][j]); } } } return P[A.length-1][m]; } }
上面的时间空间复杂度都是O(MN)
状态转移方程式：
f[i][j] = Max(f[i-1][j],f[i-1][j-A[i]]+A[i])
f[i][j]表示对前i个物品，j的空间所能够取得的最大价值
实际上，我们需要求的是对所有的n个商品在m的空间中能够放入的最大价值
可以修改定义一个一维矩阵，长度就是m的空间的价值
f[j] = Max(f[j],f[j-A[i]]+A[i]) 这里就相当于对上面的矩阵进行了压缩
public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { // write your code here int[] P = new int[m+1]; for(int i=0;i<A.length;i++){ for(int j=m;j>=0;j--){ if(j>=A[i]) P[j] = Math.max(P[j],P[j-A[i]] + A[i]); } } return P[m]; } }
参考：http://love-oriented.com/pack/P01.html
原文：http://www.cnblogs.com/theskulls/p/5487061.html