题目描述
xinjun是各类手游的狂热粉丝，因随手一氪、一氪上千而威震工大，现在他迷上了阴阳师。xinjun玩手游有一个习惯，就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用，故称圣雄肝帝)。已知阴阳师有N个模式可以操作，模式i有ai种操作，但每种模式每日只能选用一种操作，可以不选。操作j能收益vj，但需要花费体力wj点。xinjun每日拥有体力M点，求他每日最多能得到多少收益。
输入描述:
第一行一个正整数T(T<=10)，表示共有T组数据。
对于每组数据，第一行两个正整数N，M(1<=N，M<=1000)。
接下来N段数据，每段第一行一个正整数ai(1<=ai<=1000)，第二行ai个正整数vj(1<=vj<=1000)，第三行ai个正整数wj(1<=wj<=1000)。
每组数据ai之和不大于104。
输出描述:
对每组数据输出一行，即xinjun每日最多能得到多少收益。
示例1
输入
1
3 10
2
2 3
3 2
2
1 1
3 4
1
5
5
输出
9
题解：
01背包，但是独特点在于，N个模式，每个模式有ai种操作，一个模式只能用一次操作，也就是并非所有操作都参与最终受益，相同模式下只能选一个操作。
这怎么解决呢？
我们用二维数字来存受益与花费
v[i][j]表示第i个模式下第j种操作的受益
w[i][j]表示第i个模式下第j种操作的花费
那么递推方程就是
f[j] = max(f[j],f[j-w[i][k]]+v[i][k]);
三重for循环的含义
在当前容量下，枚举每一种操作，保留最佳情况
我原本以为复杂度会超，发现我想太多了，数据有点水。。
这种方法应该是算是比较简单明了
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n,m;
int f[maxn];
int c[maxn];
int w[maxn][maxn];
int v[maxn][maxn];
int t;
int main()
{
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> c[i];
for(int j = 1; j <= c[i]; ++j)
{
cin >> v[i][j];
}
for(int j = 1; j <= c[i]; ++j)
{
cin >> w[i][j];
}
}
memset(f,0,sizeof(f));
f[0] = 0;
for(int i = 1; i <= n; ++i)//模式
{
for(int j = m; j >= 0; --j)
{
for(int k = 1; k <= c[i]; ++k)//第i种操作
{
if(j>=w[i][k])
f[j] = max(f[j],f[j-w[i][k]]+v[i][k]);
}
}
}
cout << f[m] << endl;
}
return 0;
}
还有个方式：
参考
模式与模式之间都是独立的
每一个模式不是只能选一种吗？那我就挑选出最佳的操作，然后进入下一个模式，一直这样走
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
struct node{
int f;
int ne;
}dp[N];
int main (){
int T;
cin>>T;
while(T--){
int P,W;
scanf("%d %d",&P,&W);
while(P--){
int n;
scanf("%d",&n);
int w[n],v[n];
for(int i=0;i<n;i++){
scanf("%d",&v[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&w[i]);
}
for(int i=0;i<n;i++){
for(int j=W;j>=w[i];j--){
dp[j].ne=max(dp[j].ne,dp[j-w[i]].f+v[i]);
}
}
for(int i=0;i<=W;i++){
dp[i].f=dp[i].ne;
}
}
cout<<dp[W].f<<endl;
memset(dp,0,sizeof dp);
}
return 0;
}
京公网安备 11010502036488号