文章

7

粉丝

387

获赞

7

访问

67.5k

头像
必须装满的,最小价值总和的01背包问题
P1164 清华大学上机题
发布于2021年1月10日 20:42
阅读数 12.0k

本题可以将要凑的总值当做背包的容量,每一张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);
    ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发