文章
7
粉丝
387
获赞
7
访问
67.5k
本题可以将要凑的总值当做背包的容量,每一张k元邮票当做容量为k价值为1的背包,然后做01背包变种问题即可。必须保证装满,以及价值总和最小。
#include<cstdio>
#include<cstring>
#define min(a,b) (((a)<(b))?(a):(b))
const int maxv = 110;
int V, N;
int cost;
int f[maxv + 10];
bool visit[maxv + 10];
int tmp[maxv + 10], size;
inline void init() {
memset(visit, 0, sizeof(visit));
visit[0] = true;
memset(f, 0x3f, sizeof(f));
f[0] = 0;
}
inline void buildDP_01Pack_MinFull(int cost, int value) {
size = 0;
for(int v = V; v >= cost; --v) {
if(visit[v - cost]) {
if(!visit[v]) tmp[++size] = v;
f[v] = min(f[v], f[v - cost] + value);
}
}
for(int i = 1; i <= size; ++i) visit[tmp[i]] = true;
}
int main() {
while(scanf("%d%d", &V, &N) != EOF) {
init();
while(N--) {
scanf("%d", &cost);
buildDP_01Pack_MinFull(cost, 1);
}
printf("%d\n", f[V] < 0x3f3f3f3f ? f[V] : 0);
...
登录后发布评论
暂无评论,来抢沙发