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); }