DP计数问题

背包dp问题 dp[i][j] 是在前i个背包内选择价值j的方案数
状态转移方程是dp[i][j] += dp[i - 1 ][j - a[i][j]]
dp[0][0] = 1 代表的意义是在前 0 个背包 价值为 0的方案数是1

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#define  pb push_back
typedef long long ll;
using namespace std;
int a[105][105],dp[105][10000 + 10];
int n,k,m;
int main()
{
    //freopen("in.txt","r",stdin);
    cin >> n >> k ;
    dp[0][0] = 1;
    for(int i = 1; i <= n ;i ++)
    {
        cin >> m;
        for(int j = 1 ;j <= m ;j ++)
        {
            cin >> a[i][j];
            for(int k = 10000; k>= a[i][j];k--)
            {
                dp[i][k] += dp[i-1][k-a[i][j]];
            }
        }
    }
    int res = 0;
    for(int i = 0 ; i <= 10000;i++)
    {
        if(dp[n][i]<k){
            res = res + dp[n][i] * i;
            k-=dp[n][i];
        }
        else{
            res = res + k * i;
            break;
        }
    }
    cout << res <<endl;
    return 0 ;
}