背包问题II

题目描述

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

思路

动态规划。
依靠限定条件：大小为m的背包，创建结果集buf[m+1]
每次访问一个新元素A[i]，更新结果集buf[]
buf[j] = Math.max(buf[j],buf[j-A[i]]+V[i])

代码

public int backPackII(int m, int[] A, int V[]) {
        int[] buf = new int[m+1];
        for(int i = 0; i < A.length; i++){
            for(int j = m; j >= A[i]; j--){
                buf[j] = Math.max(buf[j],buf[j-A[i]]+V[i]);
            }
        }
        return buf[m];
    }

考察点

• 动态规划