0-1背包再修改版，0-1背包修改版

0-1背包再修改版，0-1背包修改版

題目描述

把錢花完了，所以單身了，單身了所以過雙“11”，過雙“11”所以把錢花完了。

今年Nova君(三號)照舊過著他暗無天日的“買買買”的雙“11”，然而因為囊中羞澀，並不能夠太任性。他的購物車中，列滿了數不清的商品，共有N件，好多商品居然還不止一件 __(:3 」∠)_ 現在Nova君要做出一個艱難的抉擇，他要從所有商品中挑出m件拼成一個訂單，請問有多少種湊單的方法呢？求訪法數對M的余數。

PS:同一種商品不作區分。

輸入

多組測試數據（不超過100組）

每組數據兩行，第一行為三個正整數N,m,M，具體意義詳見描述，第二行為N個正整數a1,a2,,,an，代表第i個商品的個數

(1<=N,ai,m<=1000，2<=M<=10000)

輸出

對於每組數據，輸出一行，表示方法總數

輸入樣例

3 3 10000
1 2 3

輸出樣例

6

題目來源：http://biancheng.love/contest/17/problem/G/index
詳情見代碼以及注釋：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int N=1010;
 5 int a[N];
 6 int b[N][N];
 7 int main()
 8 {
 9     int n,m,M;
10     while(scanf("%d%d%d",&n,&m,&M)==3)
11     {
12         for(int i = 0; i < n; i++)
13             scanf("%d",&a[i]);//每種商品的件數
14 
15         for(int i = 0; i <= n; i++)
16             b[i][0] = 1;
17 
18         for(int i = 0; i < n; i++)//n種商品
19             for(int j = 1; j <= m; j++)//挑出m件
20             {
21                 if(j -1 - a[i] >= 0)//是否大於第i中商品件數
22                     b[i+1][j] = (b[i][j] + b[i+1][j-1] - b[i][j-1-a[i]] +M)%M;
23                 else
24                     b[i+1][j] = (b[i][j] + b[i+1][j-1])%M;
25             }
26         printf("%d\n",b[n][m]);
27     }
28 
29 }

另附背包的一些模板函數：

 1 void ZoreOnePack(int cost , int weight)//0-1背包
 2 {
 3     for (int i = W ; i >= weight ; -- i)
 4         f[i] = max(f[i],f[i-weight]+cost) ;
 5 }
 6 
 7 void CompletePack(int cost , int weight)//完全背包
 8 {
 9     for (int i = weight ; i <= W ; ++ i)
10         f[i] = max(f[i],f[i-weight]+cost) ;
11 }
12 
13 void MultiPack(int cost , int weight , int num)//多重背包
14 {
15     if (num*weight>=W)
16         CompletePack(cost,weight) ;
17     else
18     {
19         int k = 1 ;
20         while (k<num)
21         {
22             ZoreOnePack(cost*k,weight*k) ;
23             num -= k ;
24             k += k ;
25         }
26         ZoreOnePack(cost*num,weight*num) ;
27     }
28 }
29 
30 void TwoZoreOnePack(int cost , int weight , int many)
31 {
32     for (int i = W ; i >= weight ; -- i)
33         for (int j = M ; j >= many ; -- j)
34             two[i][j] = max(two[i][j],two[i-weight][j-many]+cost) ;
35 }
36 
37 void TwoCompletePack(int cost ,int weight ,int many)
38 {
39     for (int i = weight ; i <= W ; ++ i)
40         for (int j = many ; j <= W ; ++ j)
41             two[i][j] = max(two[i][j],two[i-weight][j-many]+cost) ;
42 }
43 
44 void TwoMultiPack(int cost ,int weight , int many , int num)
45 {
46     if (num*weight>=W&&num*many>=M)
47         TwoCompletePack(cost,weight,many) ;
48     else
49     {
50         int k = 1 ;
51         while (k<num)
52         {
53             TwoZoreOnePack(cost*k,weight*k,many*k) ;
54             num -= k ;
55             k += k ;
56         }
57         TwoZoreOnePack(cost*num,weight*num,many*num) ;
58     }
59 }