uva 10130 SuperSale

本文主要是介绍uva 10130 SuperSale，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有t组测试数据，有N（1<=N<=1000）个物品，每个物品都有对应的价值P(1<=P<=100)和重量W(1<=W<=30)，然后有m(1<=M<=30)个人，每个人都有能背负的最大重量，问能得到的最大的价值是多少。（多个01背包）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[30005];
bool vis[30005];
struct node
{int x,y;
}coin[1005];
int main()
{int t;scanf("%d",&t);while(t--){int n,m,sum=0,ans=0;scanf("%d",&n);memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){scanf("%d%d",&coin[i].x,&coin[i].y);sum+=coin[i].y;}vis[0]=1;for(int i=0;i<n;i++){for(int j=sum;j>=coin[i].y;j--){if(vis[j-coin[i].y]){dp[j]=max(dp[j],dp[j-coin[i].y]+coin[i].x);vis[j]=1;}}}scanf("%d",&m);while(m--){int temp,imax=0;scanf("%d",&temp);for(int i=0;i<=temp;i++){imax=max(imax,dp[i]);}ans+=imax;}printf("%d\n",ans);}return 0;
}

这篇关于uva 10130 SuperSale的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---