背包问题

发表于   |   分类于   |     |  
  |  

背包问题1

问题描述：
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。
注意事项：你不可以将物品进行切割。

样例
如果有4个物品[2, 3, 5, 7]
如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。
如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。
函数需要返回最多能装满的空间大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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) {
        return backpack(m,A,0);
    }
    public int backpack(int m,int[] A,int i){
        int max=0;
        for(;i<A.length;i++){
            if(A[i]<m)
                max=Math.max(A[i]+backpack(m-A[i],A,i+1),max);
            else if(A[i]==m)
                return A[i];
        }
        return max;
    }
}

背包问题2

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？
注意事项：A[i], V[i], n, m均为整数。你不能将物品进行切分。你所挑选的物品总体积需要小于等于给定的m。
样例：
对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话，最大能够装入的价值为9。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backpack(int m,int[] A,int V[],int i){
        int max=0;
        for(;i<A.length;i++){
            if(A[i]<=m)
                max=Math.max(V[i]+backpack(m-A[i],A,V,i+1),max);
        }
        return max;
    }
}

由于递归花费的时间较长，所以本程序还需改进。递归虽好，但要善用。