雫露露的背包

原题链接：https://ac.nowcoder.com/acm/contest/83910/G

这道题除了DFS也可以用dp。

状态转移方程为：dp[ i ][ j ] = dp[ i ][ j ] + dp[ i - 1 ][ j - t ] * space[ i ][ t ]

dp[ i ][ j ]表示到第 i 个朋友为止，取到总重量为 j 的取法组合数。space [ i ][ t ]表示第 i 个朋友手里重量为 t 的礼物的数量。

#include <bits/stdc++.h>

using namespace std;
const int N = 3010, W = 3010;

int n, w;
int space[N][W]; // 第i个朋友重量为j的礼物数量
int dp[N][W]; // 取到第i个朋友为止，拥有j重量的礼物的取法数量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> w;
    for(int i = 1; i <= n; i ++ ) {
        int a; cin >> a;
        for(int j = 1; j <= a; j ++ ) {
            int b; cin >> b;
            space[i][b] ++;
        }
    }// 完成输入
    
    for(int j = 1; j <= W; j ++ ) {
        dp[1][j] = space[1][j];
    } // dp初始化
    
    for(int i = 2; i <= n; i ++ ) {
        for(int j = 1; j <= w; j ++ ) {
            for(int t = 1; t <= w; t ++) {// 从第i个朋友这里取走了t重量的礼物
                dp[i][j] = dp[i][j] + dp[i - 1][j - t] * space[i][t];
            }
        }
    }
    
    cout << dp[n][w] << endl;
}