J-流浪西邮之寻找火石碎片【经典背包变形】

题目来源：2019 ACM ICPC Xi'an University of Posts & Telecommunications School Contest

链接：https://www.jisuanke.com/contest/2382?view=challenges

Description

众所周知，由于木星引力的影响，世界各地的推进发动机都需要进行重启。现在你接到紧急任务，要去收集火石碎片，重启西邮发动机。
现在火石碎片已成为了稀缺资源，获得火石碎片需要钱或者需要一定的积分。火石碎片有大有小，越大的碎片能量越大，火石碎片的能量越大，重启的发动机的推力也就越强。但是，不只有我们在努力呀，隔壁的师大和政法也都在收集碎片，争取重启师大发动机和政法发动机，哪个高校重启的发动机推力最大，就能代表长安区大学城为世界做出贡献，从而在史书上留下浓墨重彩的一笔。
现在你有v1块钱，v2积分，能免费(免积分)收集k个火石碎片，现在总共有n个火石碎片，每个碎片需要的钱a或者积分b，碎片的能量为val。我们希望收集火石碎片，使能量的总和尽可能大，问你skyer_hxx最多可以拿到能量总和的最大值是多少？

Input
输入包含多组测试用例。
每组数据的第一行是四个整数n，v1，v2，k；
然后是n行，每行三个整数a，b，val，分别表示每个碎片的价钱，兑换所需积分，所含能量。
1 ≤ n ≤ 100
0 ≤ v1,v2 ≤ 100
0 ≤ k ≤ 5
0 ≤ a,b,val ≤ 100

Output
对于每组数据，输出能得到的最大能量值。

Sample Input
4 5 2 1

2 2 4

4 5 1

4 2 4

2 2 5

Sample Output
14
Hint
只要钱或者积分满足购买一个碎片的要求，那么就可以买下这个碎片。

题解思路：

1.每块碎片只有一个，典型的01背包变形问题。

2.dp[i][j][k]代表花费i元钱，j积分，免费换取k个碎片所能获得的最大价值。

3.对于每个物品，我们可以有3个选择：花钱，花积分，免费换取。因此四层循环，判断3种选择，更新最大值即可。

代码：

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #define mem(a, b) memset(a, b, sizeof(a))

 using namespace std;

 int n, v1, v2, k;

 int a[], b[], val[];

 int dp[][][]; //代表花费i钱,j积分和免费兑换k次所达到的最大价值 

 int main()

 {

     while(scanf("%d%d%d%d", &n, &v1, &v2, &k) != EOF)

     {

         mem(dp, );

         for(int i = ; i <= n; i ++)

             scanf("%d%d%d", &a[i], &b[i], &val[i]);

         for(int i = ; i <= n; i ++)//遍历每个碎片

         {

             for(int j = v1; j >= ; j --)//钱

             {

                 for(int l = v2; l >= ; l --)//积分

                 {

                     for(int m = k; m >= ; m --)//免费兑换

                     { //枚举了每一种状态

                         int temp = ;

                         if(j >= a[i])

                             temp = max(temp, dp[j - a[i]][l][m] + val[i]);

                         if(l >= b[i])

                             temp = max(temp, dp[j][l - b[i]][m] + val[i]);

                         if(m >= )

                             temp = max(temp, dp[j][l][m - ] + val[i]);

                         dp[j][l][m] = max(temp, dp[j][l][m]);

                     }

                 }

             }

         }

         printf("%d\n", dp[v1][v2][k]);

     }

     return ;

 }

巴特西

J-流浪西邮之寻找火石碎片【经典背包变形】

最新文章

热门文章

巴特西

J-流浪西邮之寻找火石碎片 【经典背包变形】

最新文章

热门文章

J-流浪西邮之寻找火石碎片【经典背包变形】