UVA.10130 SuperSale (DP 01背包)

2019-11-08 19:45:35

字体：大中小

来源：转载

供稿：网友

UVA.10130 SuperSale (DP 01背包)

题意分析

现在有一家人去超市购物。每个人都有所能携带的重量上限。超市中的每个商品有其相应的价值和重量，并且有规定，每人每种商品最多购买一个。求这一家人所能购买到的最大价值是多少。

每个人的所能携带的最大重量即为背包容量。此题只是换成n个人而已。所以分别以每个人最大携带重量为背包容量，对所有商品做01背包，求出每个人的最大价值。这些最大价值之和即为这家人购物的最大价值。

核心状态转移方程： dp[i][j] = max(dp[i][j],dp[i-1][j-wei[i]]+val[i]);

代码总览

/* Title:UVA.10130 Author:pengwill Date:2017-2-16*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nvmax 35#define nmax 1005#define npmax 105using namespace std;int val[nmax],wei[nmax],dp[nmax][nvmax],pw[npmax],n,tot;void _01kp(int pos){ memset(dp,0,sizeof(dp)); for(int i =1 ;i<=n;++i){ for(int j = 0;j<=pw[pos];++j){ dp[i][j] = dp[i-1][j]; if(j>=wei[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-wei[i]]+val[i]); } } tot+=dp[n][pw[pos]];}int main(){ //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--){ int P,W,G; tot = 0; scanf("%d",&n); for(int i =1; i<=n; ++i){scanf("%d%d",&P,&W); val[i] = P; wei[i] = W;} scanf("%d",&G); for(int i = 1; i<=G;++i) scanf("%d",&pw[i]); for(int i =1; i<=G;++i){ _01kp(i); } PRintf("%d/n",tot); } return 0;}

上一篇：121. Best Time to Buy and Sell Stock

下一篇：UVA.10066 The Twin Towers (DP LCS)