背包问题

题目描述

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

思路

动态规划。
动态规划与贪心的不同：
DP每次取得的新元素，都会导致刷新一遍结果集。因此DP当前取得的结果集，并不是最优解，每次取得的新元素都会改变结果集。
贪心必须保证每次取得新元素，只对当前结果产生影响，不会更新过去的结果集。所以贪心必须保证当前得到的解就是最优解。
对于这道题：
使用一个buf[m+1]的数组保存结果集。buf[i]表示背包重量为i时可以装入的最大重量。
每次访问一个元素A[i]，更新结果集buf：
buf[j] = max（buf[ j-A[i] ]+A[i]，buf[j]）
虽然buf[j]在每次访问新元素A[i]时，都表示当前承重为j的背包可以装入的最大重量，但每次新元素到来时，buf数组的值都可能改变。所以是动态的！

代码

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

考察点

• 动态规划