c/c++语言开发共享BZOJ2287: 【POJ Challenge】消失之物(背包dp)

题意 ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包,有几种方法呢?” — 这是经典的问题了。她把答案记为 Count(i, x) ,想要得到所有1 <= i <= N, …


题意

ftiasch 有 n 个物品, 体积分别是 w1w2, …, wn。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 n – 1 物品装满容积为 x 的背包,有几种方法呢?” — 这是经典的问题了。她把答案记为 count(i, x) ,想要得到所有1 <= i <= n, 1 <= x <= m的 count(i, x) 表格。

sol

orz hzwer

这题可能有三种做法吧。。

第一种是分治背包

第二种是ntt优化暴力

第三种是$o(nm)$的神仙dp

这里只说一下第三种

首先设$f[i][j]$表示前$i$个物品选了$j$个,然后就是裸的完全背包

设$cnt[i][x]$表示答案

考虑这玩意儿怎么转移

  1. $cnt[i][0] = 1$
  2. 若$j le w[i]$,$cnt[i][j] = f[n][j]$
  3. 若$j geqslant w[i]$,$cnt[i][j] = f[n][j] – cnt[i][j – w[i]]$

第三个的转移非常神仙,反正我是没想出来,我们考虑用总的方案数减去用了改物品的方案数,我们发现直接算不是很好算,然后补集转化一下,用了物品$i$,体积为$j$,那么其他物品的体积为$j – w[i]$,这里的其他物品,也就是不用$i$的情况,也就是原来的$cnt$数组!!好神仙啊qwq

#include<cstdio>  #include<algorithm>  #include<stack>  #include<queue>  #include<cmath>  //#define int long long   #define pair pair<int, int>   #define fi first  #define se second  #define mp(x, y) make_pair(x, y)  using namespace std;  const int maxn = 1e6 + 10, mod = 10;  inline int read() {      char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}      while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();       return x * f;  }  int n, m;  int w[maxn], f[2001][2001], cnt[2001][2001];  main() {      n = read(); m = read();      for(int i = 1; i <= n; i++) w[i] = read();      f[0][0] = 1;      for(int i = 1; i <= n; i++) {          for(int j = 0; j <= m; j++) {              (f[i][j] += f[i - 1][j]) %= mod;//不装               if(j >= w[i]) (f[i][j] += f[i - 1][j - w[i]]) %= mod;          }      }      for(int i = 1; i <= n; i++) {          cnt[i][0] = 1;          for(int j = 1; j <= m; j++) {              if(j < w[i]) cnt[i][j] = f[n][j] % mod;              else cnt[i][j] = (f[n][j] - cnt[i][j - w[i]] + mod) % mod;          }      }      for(int i = 1; i <= n; i++, puts(""))          for(int j = 1; j <= m; j++)              printf("%d", cnt[i][j] % mod);      return 0;  }  /*  3 2  1 1 2  */

 

www.ctvol.com true Article c/c++语言开发共享BZOJ2287: 【POJ Challenge】消失之物(背包dp)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/608239.html

(0)
上一篇 2021年5月15日 上午3:58
下一篇 2021年5月15日 上午4:00

精彩推荐