NC145 01背包

描述

已知一个背包最多能容纳体积之和为的物品，现有个物品，第个物品的体积为, 重量为，求当前背包最多能装多大重量的物品？

数据范围：

• 
• 
• 
• 

  进阶要求：时空复杂度

解决方法：动态规划

定义大小为n*V的二维数组dp，dp[i][j]表示在面对第i件物品且背包容量为j时，所能装入的最大重量 。

• 如果j<v[i]，背包容量不足以放下第i件物品，不能放入，dp[i][j]=dp[i-1][j]；

• 如果j>=v[i]，背包容量足以放下第i件物品，那就有放和不放两种情况：

  • 如果放，那么dp[i][j]=dp[i-1][j-v[i]]+w[i]，亦即前i-1件物品的最优重量+第i件物品的重量 ；
  • 如果不放，那么dp[i][j]=dp[i-1][j]，亦即前i-1件物品在容量为j时的最优重量 ；

  • 具体放还是不放，就看哪种情况下价值最大了 。

    实现代码

    class Solution {
    public:
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 计算01背包问题的结果
    * @param V int整型 背包的体积
    * @param n int整型 物品的个数
    * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
    * @return int整型
    */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
       // 全部初始化为0
       vector<vector<int> > dp(n+1, vector<int>(V+1, 0));
       for(int i=1; i<=n; i++){
           for(int j=1; j<=V; j++){
               if(j < vw[i-1][0]){
                   // 背包容积不足
                   dp[i][j] = dp[i-1][j];
               }
               else{
                   // 背包容积够，可放可不放
                   dp[i][j] = max(dp[i-1][j-vw[i-1][0]] + vw[i-1][1], dp[i-1][j]);
               }
           }
       }
       // 返回n件物品在容积为V时的最优重量即可
       return dp[n][V];
    }
    };

    运行效率评价

    运行时间：8ms，超过52.46% 用C++提交的代码；
    占用内存：4352KB，超过14.08%用C++提交的代码。