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 105

using 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;

}