一眼看上去，选与不选，很像01背包问题，很显然当k=1时就是01背包
那我们可以想到设置dp[i]，表示目标为i时所要花费的最小代价，直接套用01背包模板
但是题目写道要满足多个k值，也就是多个背包问题，那该怎么办
但是我们可以看到，p<=5,小于10进制每一位的9
那么我们可不可以把它转化成10进制来做呢
方法：
1.把目标值设为m，m的每一位都为p一共k位
2.选第i时，我们把x算出，x表示目标为x时再加上第i个项目时能到达目标j的数值，也就是转换成10进制
2.1 意思是j是由谁转移得到的
3.状态转移（01模板）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10, INF = 1e9 + 10;
int n, k, p;
int c[150];//代价
int a[150][10];//每一位的价值
LL dp[100005];//目标为i时所花费的最小代价,i最大55555，dp[i]最大1e11
int m;//10进制目标值，每一位都为p
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k >> p;
for (int i = 1; i <= k; i++) m = m * 10 + p;//目标值
for (int i = 1; i <= n; i++) {
cin >> c[i];
for (int j = 1; j <= k; j++) cin >> a[i][j];
}
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {//01背包
//十进制转换
int w[6] = {0};
for (int x = j, l = 1; l <= k; l++, x /= 10) {
w[l] = max(0, x % 10 - a[i][l]);//计算每一位的转移
}
int x = 0;
for (int l = k; l > 0; l--) x = x * 10 + w[l];//确立j由谁转移
//十进制转换
//01背包
dp[j] = min(dp[j], dp[x] + c[i]);//选第i个，目标为j时由x转移的最小代价
}
}
cout << (dp[m] > 1e11 ? -1 : dp[m]);
return 0;
}