题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2126

题意: n个物品,m元钱,每个物品最多买一次,问最多可以买几件物品,并且输出方案数。

分析:一看就想到01背包,不过得加一维来表示能买的物品件数。dp[i][j]表示在i元内至多能买j件物品。则状态转移方程为:dp[i][j]+=dp[i-a[k][j-1].

最后把在1~m元内买到的最大件数mx加起来就是题目所求。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 1000010
#define clr(a) (memset(a,0,sizeof(a)))
using namespace std;
int dp[][],a[];
int n,m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
clr(dp);
dp[][]=;
int mx=;
for(int i=;i<=n;i++)
for(int j=m;j>=a[i];j--)
{
for(int k=n-;k>=;k--)
{
if(dp[j-a[i]][k])dp[j][k+]+=dp[j-a[i]][k],mx=max(mx,k+);
}
}
if(mx==)
{
puts("Sorry, you can't buy anything.");
continue;
}
int ans=;
for(int i=;i<=m;i++)ans+=dp[i][mx];
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",ans,mx);
}
}

最新文章

  1. 使用SSH上传安装eclipse
  2. 企业IT管理员IE11升级指南【7】—— Win7和Win8.1上的IE11功能对比
  3. scala的面向对象编程
  4. php 面向对象中的魔术方法
  5. 线程----BlockingQueue (转)
  6. 开始使用Ambari吧
  7. ipconfig
  8. 将 notepad++ 添加到鼠标右键菜单 带图标
  9. 浏览器中的 JS 和 Node.js 中的 JS
  10. 【Java】maven多项目资源共享
  11. IO、NIO、AIO理解
  12. vs2012添加自定义资源步骤
  13. 在Android中使用Protocol Buffers(上篇)
  14. 为什么有时候NSData转换成NSString的时候返回nil
  15. POJ - 3111 K Best 0-1分数规划 二分
  16. Eclipse搭建Android开发环境(安装ADT,Android4.4.2)
  17. Part1.1 、RabbitMQ 操作使用
  18. var ev = ev || event
  19. ubuntu 16.04 安装googlepinyin中文输入法
  20. 【CSS】多行溢出显示省略号

热门文章

  1. APNS 那些事!
  2. Servlet的学习之Session(3)
  3. Window7下安装openssl完整版(亲测实现)
  4. catalan 数——卡特兰数(转)
  5. BUG: scheduling while atomic: events/0/4/总结
  6. ASP.NET - 分页
  7. Android菜鸟的成长笔记(8)——Intent与Intent Filter(上)
  8. Error: 17053 LogWriter: Operating system error 21(The device is not ready.)
  9. 一个计算器的C语言实现
  10. UVA 10003 Cutting Sticks