hdu2126(求方案数的01背包)
2024-10-18 23:33:08
题目链接: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);
}
}
最新文章
- 使用SSH上传安装eclipse
- 企业IT管理员IE11升级指南【7】—— Win7和Win8.1上的IE11功能对比
- scala的面向对象编程
- php 面向对象中的魔术方法
- 线程----BlockingQueue (转)
- 开始使用Ambari吧
- ipconfig
- 将 notepad++ 添加到鼠标右键菜单 带图标
- 浏览器中的 JS 和 Node.js 中的 JS
- 【Java】maven多项目资源共享
- IO、NIO、AIO理解
- vs2012添加自定义资源步骤
- 在Android中使用Protocol Buffers(上篇)
- 为什么有时候NSData转换成NSString的时候返回nil
- POJ - 3111 K Best 0-1分数规划 二分
- Eclipse搭建Android开发环境(安装ADT,Android4.4.2)
- Part1.1 、RabbitMQ 操作使用
- var ev = ev || event
- ubuntu 16.04 安装googlepinyin中文输入法
- 【CSS】多行溢出显示省略号
热门文章
- APNS 那些事!
- Servlet的学习之Session(3)
- Window7下安装openssl完整版(亲测实现)
- catalan 数——卡特兰数(转)
- BUG: scheduling while atomic: events/0/4/总结
- ASP.NET - 分页
- Android菜鸟的成长笔记(8)——Intent与Intent Filter(上)
- Error: 17053 LogWriter: Operating system error 21(The device is not ready.)
- 一个计算器的C语言实现
- UVA 10003 Cutting Sticks