UVA11450 题解

xcrr · 2022-09-27 20:20:10 · 题解

打完了才想起来这就是分组 0/1 背包模型。

由于没有翻译，我开始时理解错了题意，这里解释一下题意：

给定几个组，每个组中有一些物品，每个物品有价格。你需要在每个组中选择一个物品，求最后在花费不超过预算 m 的情况下，能花费的最大价格。

如果无法实现输出 no solution。

考虑 dp_{i,j}=0/1 表示选择第 i 组时，恰好花费 j 圆能否实现，1 代表可以，0 代表不行。

遍历每组，遍历其中每个物品（假设此物品的价格为 w），枚举 j 。当且仅当上一组的状态中，恰好花费 j-w 能实现，当前状态才能实现，那么就让我们从 dp_{i-1,j-w} 转移过来。

可以 bitset，滚动数组优化，但数据范围小，不必。

#include<bits/stdc++.h>
#define endl '\n'
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using namespace std;
int t;
const int N=30;
int w[N][N];
bool dp[N][210];
inline void solve(){
    cin>>t;
    while(t--)
    {
        int m,c;
        int k[N];
        cin>>m>>c;
        for(int i=1;i<=c;i++)
        {
            cin>>k[i];
            for(int j=1;j<=k[i];j++)
                cin>>w[i][j];
        }   
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=1;i<=c;i++)
        for(int j=1;j<=k[i];j++)
        for(int p=w[i][j];p<=m;p++)
        dp[i][p]|=dp[i-1][p-w[i][j]];
        int ans=-1;
        for(int i=m;i>=0;i--)
        if(dp[c][i]){ans=i;break;}
        if(ans==-1)cout<<"no solution\n";
        else cout<<ans<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    const int _=0;
    return ~~(0^_^0);
}