hdu 2126 Buy the souvenirs 01背包求最优方案数

缘起

背包问题还有一种问法, 就是要你求方案总数. hdu 2126 Buy the souvenirs

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n种物品，给每种物品的价格，自己的钱m，求在满足买的最多个数情况下有几种方案(每种物品至多买一件(毕竟是纪
念品嘛~买那么多干什么~))。

【输入】
多样例,第一行给出样例数. 对每个样例, 首先给出n和m,然后给出n个正整数,每个正整数就是纪念品的价格.
0<=m<=500, 0<n<=30, 价格都是正整数.

【输出】
方案数,如果买不了, 按样例输出

【样例输入】
2
4 7
1 2 3 4

4 0
1 2 3 4

【样例输出】
You have 2 selection(s) to buy with 3 kind(s) of souvenirs.
Sorry, you can't buy anything.

【限制】
1s

思路是只需要在做01背包的时候维护一下计数就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxm = 505;
int n,m, dp[maxm], dpp[maxm]; // dp[i][j]是前i件物品容量为j的最大背包值, dpp[i][j]是前i件物品容量为j的实现最大背包价值的方法数

void zo(int a)
{
	for (int v = m; v>=a; v--)
	{
		if (dp[v] < dp[v-a]+1) //  则一定要选a这个纪念品
		{
			dp[v] = dp[v-a]+1;
			dpp[v] = dpp[v-a];
		}
		else if (dp[v] == dp[v-a]+1) // 可选可不选
		{
			dpp[v] += dpp[v-a];
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d", &n, &m);
		memset(dp,0,sizeof(dp));
		fill(dpp,dpp+m+1,1); // 不选任何纪念品, 容量为j, 方法数只能是1(就是什么都不选达到最大背包价值0)
		for (int i = 1,a;i<=n;i++)
		{
			scanf("%d",&a);
			zo(a);
		}
		dp[m]?printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dpp[m], dp[m]):puts("Sorry, you can't buy anything.");
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 1756kB
Length 948
Lang C++
Submitted 2019-10-27 08:49:43
Shared
RemoteRunId 31126193