30. 有一个人前来买瓜

Discription

军训这么累，当然要吃瓜啦。

有一个小军前来买瓜。

众所周知，YHW水果摊里的西瓜的瓜皮子和瓜粒子都是金粒子做的。小军当然想获得尽可能多的金粒子。

一共有n个瓜，每个瓜有重量w，成熟度v，金粒子数量g。

虽然小军的钱是无限的，但他的电动车载重是有限的，因此他不能买总重量超过W的瓜。

"我开水果摊的，能卖给你生瓜蛋子？ ——YHW

因此，当小军买的瓜的总成熟度小于V时，YHW并不会把瓜卖给他。

具体的：水果摊一共有n个瓜，每个瓜有重量w，成熟度v，金粒子数量g。一共有q次询问，每次询问给出两个值W、V，小军要选取n个瓜的子集，使总重量 Σw≤W,总成熟度Σv≥V，求 Σg
的最大值。

Input

第一行输入两个整数,q(1≤n≤100,1≤q≤100)，代表瓜的数量和询问数量。

接下来n行，每行三个整数，第i行的三个整数为i,vi,gi(1≤wi,vi,gi≤100)，分别代表第i个瓜的重量，成熟度和价值。

接下来q行，输入两个整数,V(1≤W,V≤500)，代表一组询问。

Output

输出一共有q行，每行一个整数，分别代表每组询问的最大金粒子数总和，若无合法的买法则输出-1。

思路

比背包问题多了一个维度。可以使用 dp[j][k] 储存当质量为j且成熟度为k时的金粒，（与空间优化后的背包同理，质量和成熟度需要从大到小遍历，防止覆盖数据）。三维肯定会超时。

只需要进行一次动态规划，对于每一次对话查表就OK

初始化;状态转移方程参考背包问题。额外注意的是当成熟度大于500时可以直接放在500里面，减少空间。

代码

#include <stdio.h>
#include <string.h>
#define N 102
#define M 500
int dp[M+1][M+1];
int max(int a, int b)
{
    return a > b ? a : b;
}
int min(int a, int b)
{
    return a < b ? a : b;
}
int main(int argc, char const *argv[])
{
    int n, q, i, j, k, W, V;
    int w[N], v[N], g[N];
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    
    scanf("%d %d", &n, &q);    
	for (i = 1; i <= n; i++){
		scanf("%d %d %d", &w[i], &v[i], &g[i]);
	}
        
    for (i = 1; i <= n; i++)
    {
        for (j = M; j >= 0; j--)
        {
            for (k = M; k >= 0; k--)
            {				
				if(dp[j][k]==-1 || j+w[i]>500)	continue;
				dp[j+w[i]][min(k+v[i],M)]=max(dp[j][k]+g[i],dp[j+w[i]][min(k+v[i],M)]);
            }
        }
    }

    for (i = 0; i < q; i++)
    {
        scanf("%d %d", &W, &V);
        int gold = -1;
        for (j = 0; j <= W; j++)
        {
            for (k = V; k <= M; k++)
            {
                if (dp[j][k] > gold && dp[j][k])
                    gold = dp[j][k];
            }           
        }

		printf("%d\n", gold);
    }

    return 0;
}