题意:

  给出一些纪念品的价格,先算出手上的钱最多能买多少种东西k,然后求手上的钱能买k种东西的方案数。也就是你想要买最多种东西,而最多种又有多少种组合可选择。

思路:

  01背包。显然要先算出手上的钱m最多能买多少种东西k,可以从价格最少的纪念品买起,看最多能买多少种,置为k。接下来按照常规01背包计算,需要记录下方案数和组成的物品数,看代码就会懂的。

 #include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n, m, k, sum;
int p[N],cbn[][N];
int cal()
{
memset(cbn,,sizeof(cbn));
cbn[][]=; //必要的初始化
for(int i=; i<n ;i++) //对于每件物品
{
for(int j=m; j>=p[i]; j--) //对于每种价格
{
for(int e=; e<=n; e++) //组成j价格的方案数是cbn[j]的总和,其中下标e表示由e种纪念品组成的。
cbn[j][e+]+=cbn[j-p[i]][e];
}
}
int cnt=;
for(int i=m; i>=sum; i--) //价格在sum~m,其组合物品数为k的方案数,统计起来就是答案。
cnt+=cbn[i][k];
return cnt;
}
int main()
{
//freopen("input.txt","r",stdin);
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=; i<n; i++) scanf("%d", &p[i] );
sort(p, p+n);
for(sum=k=; k<n; k++)
{
sum+=p[k];
if(sum>m)
{
sum-=p[k]; //这个sum有用的,是买最多件物品的最少价格。
break;
}
} if(k==) //没钱
{
printf("Sorry, you can't buy anything.\n");
continue;
}
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", cal(), k );
}
return ;
}

AC代码

最新文章

  1. mysql java Cannot find the driver in the classpath!
  2. 后台输出HTML
  3. Google Cardboard
  4. python 学习笔记 copy
  5. android应用框架搭建------BaseActivity
  6. Linux常用操作
  7. js:通过正则匹配获取页面的url中的参数
  8. Rookey.Frame v1.0 视频教程发布了
  9. Promise及Async/Await
  10. SSRF绕过filter_var(),preg_match()和parse_url()
  11. 阿里云服务器CentOS7怎么分区格式化/挂载硬盘
  12. git pull 提示 There is no tracking information for the current branch
  13. [转]SQL Server 中WITH (NOLOCK)浅析
  14. Hive学习之路 (六)Hive SQL之数据类型和存储格式
  15. PyQt5教程——菜单和工具栏(3)
  16. Elasticsearch入门教程
  17. shell 字符串加入变量
  18. Jira 6.0.5的详细安装及汉化授权
  19. openlayers研究(一) 初始化流程
  20. vue bus方式解决非父子组件间的传值

热门文章

  1. 流媒体中ffmpeg 命令的使用
  2. Oracle&amp;nbsp;11gr2的完全卸载
  3. VNC协议分析
  4. ASP.NET中 TextBox 文本输入框控件的使用方法
  5. LightOJ - 1234 LightOJ - 1245 Harmonic Number(欧拉系数+调和级数)
  6. AutoHotkey常用配置
  7. Redis在windows实现将数据缓存起来定时更新读取
  8. 大白话5分钟带你走进人工智能-第二十六节决策树系列之Cart回归树及其参数(5)
  9. 关于通过angularJs将页面中的html table 导出生成excel
  10. hdu1506 直方图中最大的矩形 单调栈入门