NOWCODER xinjun与阴阳师(01背包变形)

链接：https://ac.nowcoder.com/acm/problem/14602
来源：牛客网

题意：

N种物品，M点体力
每种物品有a[i]个，每个物品重量w[j],价值v[j]
每种物品只能选一个，可选可不选
初始体力为M，求价值之和最大值

思路：

01背包变形
01背包模板是对n个物品取一定代价下的最大价值，
但是这道题对于每种物品，有a[i]个物品可选且只能选一个，相当于变成了一个二维数组
那我们在每种物品下加一层循环就可以了，然后按照01背包的思路去写

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10; 
int t,n,m,a[maxn],v[maxn][maxn],w[maxn][maxn],dp[maxn]; 
int main() {cin>>t;while(t--) {cin>>n>>m;//n种模式，m点体力for(int i=1; i<=n; i++) {cin>>a[i]; //第i种物品有a[i]个for(int j=1; j<=a[i]; j++) cin>>v[i][j];//价值 for(int j=1; j<=a[i]; j++) cin>>w[i][j];//代价 }memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++) { //模式for(int j=m; j>=0; j--) { //体力for(int k=1; k<=a[i]; k++) { //第n种物品第k个if(j>=w[i][k]) {//dp[i]代表代价i所获得的最大价值 dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);}    }}}cout<<dp[m]<<endl;}
}