【题解】玩具
【题目描述】
商店正在出售蒜头君最喜欢的系列玩具,在接下来的 " 周中,每周会出售其中的一款,同一款玩具不会重复出现。由于是蒜头君最喜欢的系列,他希望尽可能多地购买这些玩具,但是同一款玩具蒜头君只会购买一个。同时,蒜头君的预算只有元,因此他无法将每一款都纳入囊中。此外,蒜头君不能连续两周都购买玩具,否则他会陷入愧疚。现在蒜头君想知道,他最多可以买多少款不同的玩具呢?
【输入格式】
输入共2行:
第一行两个正整数几和 m,中间用一个空格隔开;
第二行共几个正整数,第i个正整数表示第:周出售的玩具的价格
【输出格式】
输出文件只有一行,包含一个整数,表示蒜头君最多能买多少款不同的玩具,
【数据范围】
对于 30%的数据,n< 10,m< 100;
对于 60%的数据,n< 100,m< 1000;
对于 100% 的数据,n< 1000,m< 50000,单个玩具的价格< 1000。
------------------------------
【题目分析】
很显然,这个题目是一个背包问题,我们设置 dp 数组为 dp|ij],表示第i周预算为j的最多可以买多少款不同的玩具。
通过转移方程 dp[i][j]= max(dp[i-1][j],dp[i-2][j-a[i]]+ 1);和 dp[i][j|= dp[i- 1][j]; 进行转移即可。
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。