01背包问题

例101背包

01背包问题就是一个背包只能选0次或者1次，求相关值的问题

算法原理

• 线性动态规划，我们尝试设置dp[i][j] 从1到i号背包，体积小于等于V的最大重量.

• dp表的更新，根据最后一步分类判断
  

• 若不选i位置，则dp[i][j] = dp[i-1][j];

• 若选i位置，则dp[i][j] = dp[i-1][j-nums[i]] + nums[i];

• 注意选 i 位置的时候 j > nums[i]

• 取两者最大值

代码实现

特别注意 dp[x][X] 和 vw[i][j] 的映射关系
因为dpdp[x][V] 从1到x号背包，体积小于等于V的最大重量.
下标从1开始，而vw[i][j] 下标从 0开始所以 x - 1= j

int dp[1010][1010]; // 从1到i号背包，体积小于等于V的最大重量
    int knapsack(int V, int n, vector<vector<int> >& vw) {
       for(int i = 1; i <= n; i++)
       {
            for(int j = 0; j <= V ; j++)
            {
                int tmp1 = 0,tmp2= 0;
                if(j - vw[i-1][0] >=0)
                {
                    tmp1 = dp[i-1][j-vw[i -1][0]] + vw[i-1][1];
                }
                tmp2 = dp[i-1][j];
              //  printf("tmp1:%d tmp2:%d\n",tmp1,tmp2);
                dp[i][j] = max(tmp1,tmp2);
            }
       } 
      
        return dp[n][V];
    }

例2装箱问题

代码实现

#include
using namespace std;
int dp[31][20010];  // 表示从 0 到 i 号物品 容量小于V等于 的 最大空间 
int main()
{
    int v = 0 , n = 0;
    int arr[20010];
    cin >> v >> n;
    for(int i = 1 ; i <= n; i++)
        cin >> arr[i];
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 0 ; j <= v ; j++)
        {
            if(j >= arr[i])
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-arr[i]] + arr[i]);
            else 
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << v - dp[n][v] << endl; 
    return 0;
}