背包问题题

文章目录

1. 0-1背包步骤

  1. dp数组的含义：纯0-1背包：有若干种物品，每种选一个，一个背包最多能装多大价值（可以不用装满）
  2. 设置初始值：我见过的一般都是0，只有dp[j]+=dp[j-nums[i]]这种才是1，因为如果是0就始终是0了
  3. 遍历顺序：纯0-1先正向遍历物品，再逆向遍历容量
  4. 打印dp数组

dp数组含义：
纯0-1：这个容量的背包的最大价值
分割等和子集：这个包能装满吗？（价值等于重量）
最后一块石头的重量：这个背包最多能装多少（这一道和上面那道差不多）
目标和：这个背包最多能有多少种方法
一和零：这个背包最多能装多少个物品

初始化：上面这些题初始化只有那个目标和第一个参数不是0，因为目标和时+=，其它都是max，目前先按照这个规律记着，后续出问题再说。

0-1背包遍历顺序：
第一个for用于遍历物品，自然是把数组从头遍历到尾
第二个for用于倒序遍历容量，初始值自然是数组的最大值，退出情况就是数组越界的情况。
不是计算次数，单纯计算大小的：

vector<int>product;//<物品
int capacity;//<容量

vector<int>dp(capacity+1,0);//<dp大小为容量+1
for(int i=0;i<product.size();++i)//<先遍历物品
{
	for(int j=dp.size()-1;j-product[i]>=0;--j)//<再遍历容量，倒序遍历，满足不越界条件
	{
		dp[j] = max(dp[j],dp[j-product[i]]+product[i]);
	}
}

计算次数

vector<int>product;//<物品
int capacity;//<容量

vector<int>dp(capacity+1,0);//<dp大小为容量+1
dp[0]=1;
for(int i=0;i<product.size();++i)//<先遍历物品
{
	for(int j=dp.size()-1;j-product[i]>=0;--j)//<再遍历容量，倒序遍历，满足不越界条件
	{
		dp[j] += dp[j-product[i]]+product[i];
	}
}

2. 完全背包步骤

  1. dp数组的含义：纯完全背包：有若干种物品，每种无限个，一个背包，最多能装多大的价值（当然可以不装满）
  2. 设置初始值：我见过的一般都是0，只有+=这种才是1，因为如果是0就始终是0了
  3. 遍历顺序：纯完全背包不在乎遍历顺序，都是物品和容量都是正序遍历。不过遍历容量的时候都得是0到size大小，判断数组是否越界单加一个if。如果是先遍历物品再遍历容量，和0-1一样的时候，是组合数（无序），先遍历容量再遍历物品是排列数（有序）
  4. 打印dp数组

完全背包：
和0-1背包几乎一样，传统的完全背包先遍历物品还是先便利容量是无所谓的。

组合数，122和221不再重复计算。

vector<int>product;//<物品
int capacity;//<容量

vector<int>dp(capacity+1,0);//<dp大小为容量+1
for(int i=0;i<product.size();++i)//<先遍历物品
{
	for(int j=0;j<dp.size();;++i)//<再遍历容量，倒序遍历，满足不越界条件
	{
		if(j-product[i]>=0)
		{
			dp[j] = max(dp[j],dp[j-product[i]]+product[i]);
		}
	}
}

排列数，122和221是两种情况。

vector<int>product;//<物品
int capacity;//<容量

vector<int>dp(capacity+1,0);//<dp大小为容量+1
for(int j=0;j<dp.size();;++i)//<先遍历容量，倒序遍历，满足不越界条件
{
	for(int i=0;i<product.size();++i)//<再遍历物品
	{
		if(j-product[i]>=0)
		{
			dp[j] = max(dp[j],dp[j-product[i]]+product[i]);
		}
	}
}

3. 三种遍历顺序的关系

三种分别是：先正序遍历物品，后倒序遍历容量；先正序遍历物品，后正序遍历容量；先正序遍历容量，再正序遍历物品

先搞一个例子：有一组物品，它们的重量是weight，价值是value，包的重量是bagweight

  vector<int> weight = {1, 3, 4};
  vector<int> value = {1, 2, 3};
  int bagweight = 10;
3.1 0-1背包和普通完全背包

0-1背包是先正序遍历物品，后倒序遍历容量，普通完全背包只要都是正序，先遍历物品还是先遍历容量都可以。

再重新说一下dp[j]数组的含义，我理解是在[0,i]范围内长度为j时满足的内容。但是这个“[0,i]”的理解虽然正确，但是不方便理解，换个说法：每次到一圈新的for就相当于在上一圈的情况下新加一个物品。

滚动数组的方法处理时，倒序用的是上一次的结果，正序用的是这一次的结果

两个例子

0-1背包

void vec1(const vector<int> &weight, const vector<int> &value, int bagweight) {
  vector<int> dp(bagweight + 1, 0);
  for (int i = 0; i < (int)weight.size(); i++) {    // 遍历物品
    for (int j = bagweight; j >= weight[i]; j--) {  // 遍历背包容量
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
      for (auto x : dp) cout << x << ",";
      cout << endl;
    }
  }
}

能看出数据都是一圈一圈完成的。外层的for跑玩一圈表示多使用一个物品。

下面的第1行和第11行都是在背包容量为10的时候第一次添加新物品。递推公式中 d p [ j ] dp[j] dp[j]是上一圈的结果， d p [ j − w e i g h t [ i ] ] dp[j - weight[i]] dp[j−weight[i]]也是上一圈的结果，相当于物品只能用一次。

0-1
0,0,0,0,0,0,0,0,0,0,1,#能看出此时只有下标为10的更新了，剩下值为0的还是上一圈（i=-1不存在就是初始值）的结果
0,0,0,0,0,0,0,0,0,1,1,
0,0,0,0,0,0,0,0,1,1,1,
0,0,0,0,0,0,0,1,1,1,1,
0,0,0,0,0,0,1,1,1,1,1,
0,0,0,0,0,1,1,1,1,1,1,
0,0,0,0,1,1,1,1,1,1,1,
0,0,0,1,1,1,1,1,1,1,1,
0,0,1,1,1,1,1,1,1,1,1,
0,1,1,1,1,1,1,1,1,1,1,
0,1,1,1,1,1,1,1,1,1,3,#此时只有下标为10的才是i=1的，其余下标都还是i=0的结果
0,1,1,1,1,1,1,1,1,3,3,
0,1,1,1,1,1,1,1,3,3,3,
0,1,1,1,1,1,1,3,3,3,3,
0,1,1,1,1,1,3,3,3,3,3,
0,1,1,1,1,3,3,3,3,3,3,
0,1,1,1,3,3,3,3,3,3,3,
0,1,1,2,3,3,3,3,3,3,3,
0,1,1,2,3,3,3,3,3,3,6,
0,1,1,2,3,3,3,3,3,6,6,
0,1,1,2,3,3,3,3,6,6,6,
0,1,1,2,3,3,3,5,6,6,6,
0,1,1,2,3,3,4,5,6,6,6,
0,1,1,2,3,4,4,5,6,6,6,
0,1,1,2,3,4,4,5,6,6,6,

void vec2(const vector<int> &weight, const vector<int> &value, int bagweight) {
  vector<int> dp(bagweight + 1, 0);
  for (int i = 0; i < (int)weight.size(); i++) {    // 遍历物品
    for (int j = weight[i]; j <= bagweight; j++) {  // 遍历背包容量
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
      for (auto x : dp) cout << x << ",";
      cout << endl;
    }
  }
}

和0-1背包一样都是先遍历物品，因此都是按行遍历，外层的for跑完一圈表示多使用一个物品。

下面的第1行和第11行都是在背包容量为10的时候第一次添加新物品。递推公式中 d p [ j ] dp[j] dp[j]是上一圈的结果， d p [ j − w e i g h t [ i ] ] dp[j - weight[i]] dp[j−weight[i]]却是这一圈的结果，而且已经用过了weight[i]，相当于物品已经用了好几次。

all
0,1,0,0,0,0,0,0,0,0,0,
0,1,2,0,0,0,0,0,0,0,0,
0,1,2,3,0,0,0,0,0,0,0,
0,1,2,3,4,0,0,0,0,0,0,
0,1,2,3,4,5,0,0,0,0,0,
0,1,2,3,4,5,6,0,0,0,0,
0,1,2,3,4,5,6,7,0,0,0,
0,1,2,3,4,5,6,7,8,0,0,
0,1,2,3,4,5,6,7,8,9,0,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
0,1,2,3,4,5,6,7,8,9,10,
3.2 考虑顺序的完全背包和不考虑顺序的完全背包

无序的完全背包是先正序遍历物品，后正序遍历容量；有序的完全背包是先正序遍历容量，再正序遍历物品。

有一组数据，和一个背包，要把背包装满，最多有多少种办法，没个数据可以用若干次（完全背包），分为在乎顺序和不在乎顺序。

  vector<int> a = {1, 2, 5};
  int bagweight = 5;

不在乎顺序的：

int change(int amount, vector<int>& coins) {
  vector<int> dp(amount + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < static_cast<int>(coins.size()); ++i) {
    for (int j = 0; j < static_cast<int>(dp.size()); ++j) {
      if (j - coins[i] >= 0) {
        dp[j] += dp[j - coins[i]];
        for (auto x : dp) cout << x << ",";
        cout << endl;
      }
    }
  }
  return dp.back();
}

每for一圈最外圈，相当于用完一种物品。数组的顺序是1,2,5。因此顺序是固定的，先选1,再选2,再选5,不可能出现2,1,5的情况。

unordered
1,1,0,0,0,0,
1,1,1,0,0,0,
1,1,1,1,0,0,
1,1,1,1,1,0,
1,1,1,1,1,1,
1,1,2,1,1,1,
1,1,2,2,1,1,
1,1,2,2,3,1,
1,1,2,2,3,3,
1,1,2,2,3,4,

在乎顺序的：

int change2(int amount, vector<int>& coins) {
  vector<int> dp(amount + 1, 0);
  dp[0] = 1;
  for (int j = 0; j < static_cast<int>(dp.size()); ++j) {
    for (int i = 0; i < static_cast<int>(coins.size()); ++i) {
      if (j - coins[i] >= 0) {
        dp[j] += dp[j - coins[i]];
        for (auto x : dp) cout << x << ",";
        cout << endl;
      }
    }
  }
  return dp.back();
}

这个是列遍历，每for完一次最外圈，相当于搞定了一种容量，这种容量的所有物品都搞定了。至于2,2这种情况为啥只计算了一次，而不是两次2,2，我也不知道，这些理解用于方便背套路就行。

ordered
1,1,0,0,0,0,
1,1,1,0,0,0,
1,1,2,0,0,0,
1,1,2,2,0,0,
1,1,2,3,0,0,
1,1,2,3,3,0,
1,1,2,3,5,0,
1,1,2,3,5,5,
1,1,2,3,5,8,
1,1,2,3,5,9,

4. 关于背包满不满的问题。

简单来说的话，标准0-1都是可以不满的，这个取决于初始值和递推公式。一般0-1初始值是全0,递推公式都是dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])。当i=0的时候，这行dp的dp[j]就是0（不选这个物品）,所以这个max返回的一定是第二项，而第二项就是选择这个物品，选第二项的时候根本没有考虑满不满，因此这种情况背包可以不满。

下一种情况是有多少种方法，dp[j] += dp[j-nums[i]]，这种情况dp[0]初始化时为1。而这种情况必须满，才能有结果。

因此统计最多能装多少，包含不满；如果怎么怎么样有多少种办法，得是满的