完全背包+最值问题

83 阅读 0 评论 55 点赞

我是靠谱客的博主震动板栗，最近开发中收集的这篇文章主要介绍完全背包+最值问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在解决完全背包问题时，通常会遇到两种问题，一种是恰好将背包装满，一种是不要求恰好装满。是否恰好装满只是初始化的会有区别。

恰好装满
如果要求恰好装满背包，那么在初始化时除了f[0]为0，其它f[1..V]均设为-∞（求最小值设为∞），这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

不一定恰好装满
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了（转自军魂）

另一种是完全背包的最值问题，一种是求最小值，一种是求最大值。恰好填满求最大值，初值设置为-∞；求最小值设为∞；不要求恰好填满就是设置为0。然后是在贪心的时候策略问题，最大选用max( ),最小选用min( ).

Piggy-Bank

题意：一个存钱罐空和满的时候重量分别为E,F，给出N种硬币的价值p[i]和重量w[i]，求使存钱罐达到F重量使用的硬币总价值最小为多少。

数据范围：1 <= E <= F <= 10000，1 <= N <= 500，1 <= P <= 50000, 1 <= W <=10000

可以转化为把背包填满，需要的最小花费。一个完全背包问题，但是求最小价值，不是最大价值。

复杂度：一重for循环枚举N种物品，一重for枚举V=F-E，O(N*F)=O(5e6)，可做。

因为恰好填满求最小值，初始值d[0]=0,f[1…maxn]设置为∞.然后f[v]!=∞,有解，否则无解。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn=505,maxm=1e4+5;
const int INF=0x3f3f3f3f;
int p[maxn],w[maxn];
int f[maxm];

int main()
{
    int t;
    scanf("%d",&t);
    int E,F;
    while(t--)
    {
        scanf("%d%d",&E,&F);
        int v=F-E,n;
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
            scanf("%d%d",&p[i],&w[i]);
        memset(f,INF,sizeof(f));
        f[0]=0;

        for(int i=1; i<=n; ++i)
        {
            for(int j=0; j<=v; ++j)
            {
                if(j>=w[i])
                    f[j]=min(f[j],f[j-w[i]]+p[i]);
            }
        }
        
        if(f[v]!=INF) printf("The minimum amount of money in the piggy-bank is %d.n",f[v]);
        else printf("This is impossible.n");
    }
    return 0;
}