joyoi 邮票问题 完全背包

缘起

日常浪费生命~ joyoi 邮票问题

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给定一个信封，最多只允许粘贴N（N≤100）张邮票，我们现在有M（M≤100）种邮票，面值分别为：X1，X2……
Xm（Xi≤255为正整数），并假设各种邮票都有足够多张。
要求计算所能获得的邮资最大范围。即求最大值MAX，使1-MAX之间的每一个邮资都能得到。
例如：N=4，有2种邮票，面值分别为1分，4分，于是可以得到1-10分和12分，13分，16分邮资，由于得不到11分
和15分，所以邮资的最大范围max=10

【输入】
第一行为最多粘贴的邮票张数n。第二行为邮票种数m。以下m行各有一个数字表示邮票的面值。

【输出】
仅一个数，最大的max的值。

【样例输入】
4
2
1
4

【样例输出】
10

【限制】
1s

本题的思路是这样的. 首先得到最多能凑 V=max*N 币值的邮票. 然后对 [0,V]中的每个面额v, 求出要凑出v最少要使用多少张邮票（物品）这样的问题. 如果>n的话, 那就是办不到. 所以从1开始, 第一个使用最少物品数>=n的就是答案.

即本题要解决的抽象问题是

1
2
有n种硬币，面值分别为V1，V2，……Vn，每种都有无限多。给定一个非负整数S，可以选用多少个硬币，
使得面值之和恰好为S？输出硬币数码的最大值和最小值。若无解，则输出-1。

而此抽象问题的dp模型是, 

1
2
3
4
5
6
7
令dp[i][j]表示前i种硬币能达到面值j的最少硬币数目(最大也是一样做的). 则
dp[i][j]=min{dp[i-1][j],dp[i][j-c[i]]+1}
没错,还是区分为取或者不取第i枚硬币.
dp[0][0] = 0, dp[0][v] = inf, 0<v<=V 因为是求inf嘛~
滚动一波数组就是
dp[v] = min{dp[v], dp[v-c[i]]+1}
dp[0]=0, dp[v] = inf(0<v<=V)

于是不难写下如下ac代码

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxv = 30000, maxn = 105;
int n,m, dp[maxv], c[maxn],s,V;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for (int i = 1;i<=m;i++)
	{
		scanf("%d", c+i);
		s = max(s, c[i]);
	}
	V = s*n;
	for (int i = 1;i<=m;i++)
	{
		for (int v = c[i]; v<=V; v++)
		{
			dp[v] = min(dp[v], dp[v-c[i]]+1);
		}
	}
	int ans = 0;
	while(dp[ans]<=n)
	{
		++ans;
	}
	printf("%d", --ans);
	return 0;
}

as情况

Accepted

#1 Accepted 0ms 2.90MiB
#2 Accepted 0ms 2.84MiB
#3 Accepted 0ms 2.82MiB
#4 Accepted 0ms 2.87MiB
#5 Accepted 0ms 2.84MiB