洛谷Genius_Star大佬的思路

思路:因为跟正常的背包不太一样  正常背包容量固定 所以输出的时候输出背包容量上限就行
1.但是这题符合条件的最小代价时 各个属性的p值都>= 5 而不是等于5因此要做特殊处理
对于每维状态x, 取min(h[@], item[i].a[@] + a@)@ = 1~5.
其中h[@]表示目标属性值p
a@为枚举的状态值
这样就把所有符合条件的大于5的属性都归为5.

2.关于五维数组，题目只说小于等于5种属性 不一定是五种 怎么处理呢
首先，输出的代价是f[h[1]][h[2]][h[3]][h[4]][h[5]] 那么只要不给h赋值那么这一维就为0
在五维状态循环中也是从h[@]开始循环，具有一般性，极大减少了码量
3.
最后就是经典的01背包状态转移方程 
f[x1][x2][x3][x4][x5] = min(f[x1][x2][x3][x4][x5], f[a1][a2][a3][a4][a5] + item[i].w);
因为这里相当于01中的滚动数组之后的遍历 因此v（h[@])从大到小枚举
4.
因为取最小代价 因此f都赋最大INF 只需给全0初值赋0即可

code:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef long long ll;
// ll INF = 1e18;
ll f[6][6][6][6][6];
struct node{
    int a[6];
    ll w;
}item[N];
int n, k, p;
int h[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> p;
    memset(f, 0x3f, sizeof f);
    for(int i = 1;i <= k;i++)h[i] = p;
    for(int i = 1;i <= n;i++){
        cin >> item[i].w;
        for(int j = 1;j <= k;j++){
            cin >> item[i].a[j];
        }
        f[0][0][0][0][0] = 0;
        for(int a1 = h[1];a1 >= 0; a1--)
            for(int a2 = h[2];a2 >= 0;a2--)
                for(int a3 = h[3];a3 >= 0;a3--)
                    for(int a4 = h[4];a4 >= 0;a4--)
                        for(int a5 = h[5];a5 >= 0;a5--){
                            ll x1 = min(h[1], a1 + item[i].a[1]);
                            ll x2 = min(h[2], a2 + item[i].a[2]);
                            ll x3 = min(h[3], a3 + item[i].a[3]);
                            ll x4 = min(h[4], a4 + item[i].a[4]);
                            ll x5 = min(h[5], a5 + item[i].a[5]);
                        f[x1][x2][x3][x4][x5] = min(f[x1][x2][x3][x4][x5], f[a1][a2][a3][a4][a5] + item[i].w);
                    }
    }
    if(f[h[1]][h[2]][h[3]][h[4]][h[5]] == 0x3f3f3f3f3f3f3f3f)cout << -1;
    else cout << f[h[1]][h[2]][h[3]][h[4]][h[5]];
    return 0;
}