· 假设此时已求出标准完全背包，用$f[j]$表示。
· 本题关键在于，由于有个数限制，那么可以强制令当前状态不满足限制，即若最多取$Have[i]$个，强制令其先取$Have[i] + 1$个，那么减去$f[S - (Have[i] + 1)]$即可，当然需用容斥原理来进行加减。
· 代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 typedef long long LL; 8 9 const int MAXN = 4 + 5; 10 const int MAXV = 1e05 + 10; 11 12 LL f[MAXV]= {0}; 13 14 const int N = 4; 15 16 int W[MAXN]; 17 int Have[MAXN]; 18 19 int T; 20 21 void Preparation () { 22 f[0] = 1; 23 for (int i = 1; i <= N; i ++) 24 for (int j = W[i]; j <= MAXV - 10; j ++) 25 f[j] += f[j - W[i]]; 26 } 27 28 int main () { 29 for (int i = 1; i <= N; i ++) 30 scanf ("%d", & W[i]); 31 scanf ("%d", & T); 32 33 Preparation (); 34 35 for (int Case = 1; Case <= T; Case ++) { 36 int S; 37 for (int i = 1; i <= N; i ++) 38 scanf ("%d", & Have[i]); 39 scanf ("%d", & S); 40 41 LL ans = 0; 42 int MAX = (1 << N) - 1; 43 for (int state = 0; state <= MAX; state ++) { 44 int rest = S; 45 int cnt = 0; 46 for (int k = 1; k <= N; k ++) 47 if (state & (1 << (k - 1))) 48 cnt ++, rest -= (Have[k] + 1) * W[k]; 49 50 if (rest < 0) 51 continue; 52 53 ans -= ((cnt & 1) ? 1 : - 1) * f[rest]; 54 } 55 56 printf ("%lld ", ans); 57 } 58 59 return 0; 60 } 61 62 /* 63 1 2 5 10 2 64 3 2 3 1 10 65 1000 2 2 2 900 66 */