德州企业网站建设要素,自己做网站卖货多少钱,做中介卖房子开哪个网站,wordpress影视主题下载失败题目链接 题意#xff1a;给出n组物品#xff0c;每组物品的物品数量不同#xff0c;要求每组中只能选一件物品#xff0c;问m容量的最大价值 思路#xff1a;实际上本题的本质还是01背包#xff0c;只不过01背包是每一种物品只能选1次#xff0c;而分组背包是每组物品只…题目链接 题意给出n组物品每组物品的物品数量不同要求每组中只能选一件物品问m容量的最大价值 思路实际上本题的本质还是01背包只不过01背包是每一种物品只能选1次而分组背包是每组物品只能选一件物品并且只能选一次所以我们dp[i][j]就变成了取前i组物品在容量不超过j的最大价值在枚举每一层的所有容量时只需要再加一层循环遍历当前组中的每一件物品即可 ac代码
#includebits/stdc.h
#define endl \n
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
// #define int unsigned long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pairint,int pii;
const int N110;
int dp[N];
int v[N][N],w[N][N],s[N];
int n,m;
void solve()
{cinnm;for(int i1;in;i){cins[i];for(int j1;js[i];j){cinv[i][j]w[i][j];}}for(int i1;in;i){for(int jm;j0;j--){for(int k1;ks[i];k){if(v[i][k]j)dp[j]max(dp[j],dp[j-v[i][k]]w[i][k]);}}}coutdp[m]endl;
}
signed main()
{Mirai;int T1;//cinT;while(T--){solve();}
}
