bzoj-2287___POJ Challenge —— 删除背包

本文主要是介绍bzoj-2287___POJ Challenge —— 删除背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门（原题目好像在OJ上消失了，真是诡异）

题目大意：

  简单的背包，问第$i$个物品消失（$i$从$1$到$n$），装满容积为$x$的背包的方案数（$x$从$1$到$m$），输出$i$与$m$的矩阵

解题思路：

  一开始简单的想从$1$遍历到$n$去算第$i$个物品消失的影响，但在仔细一想发现不对经。后来想了一下发现应该用再用一次dp来优化复杂度，即先求出物品不消失的所有背包方案数，然后再遍历依次求每个物品消失时，背包方案数。

代码思路：

  先01背包套个模板，然后物品依次消失的时候，这里和01背包思想不一样
  $①$当容量$j<w[i]$时，很明显总方案数就是当前容量$j$的方案数
  $②$但当容量$j>=w[i]$时，当前容量$j$的方案数就等于总方案数$-$容量$j-w[i]$的方案数
  这样来判断时，我们的容量$j$就要从$1$遍历到$m$，因为每次转移时要从没有这个物品的状态转移

核心：很经典的双重dp，理解好了可以加深dp的思想

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 5;
int n, m;
int w[maxn], v[maxn];
int dp[maxn][maxn], all[maxn];int main() {scanf("%d%d", &n, &m);for(int i=0; i<n; i++)scanf("%d", &w[i]);memset(dp, 0, sizeof(dp));for(int i=0; i<n; i++) {all[0] = 1;for(int j=m; j>=w[i]; j--) {all[j] += all[j - w[i]];all[j] %= 10;}}for(int i=0; i<n; i++) {dp[i][0] = 1;for(int j=1; j<=m; j++)if(j>=w[i]) {dp[i][j] = all[j] - dp[i][j-w[i]] + 10;dp[i][j] %= 10;} else {dp[i][j] = all[j];}}for(int i=0; i<n; i++) {for(int j=1; j<=m; j++)printf("%d", dp[i][j]);printf("\n");}
}

这篇关于bzoj-2287___POJ Challenge —— 删除背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---