2G Piggy Bank

#include<bits/stdc++.h>
using namespace std;
int dp[10005];
int data77[505][2];
int minhh(int x,int y)
{
    if(x<=y)return x;
    else return y;
}
int main() 
{    
    int n,E,F,N,i,j;
    scanf("%d",&n);
    while(n--)
    {
        memset(dp,-1,sizeof(dp));//初始化主要是为了初始化-1 
        dp[0]=0;//背包容量为0时,被填满 
        scanf("%d %d %d",&E,&F,&N);
        for(i=1;i<=N;i++)
        {
            scanf("%d %d",&data77[i][0],&data77[i][1]);    
        }
    //完全背包问题,滚动数组正向遍历,不可能情况为-1    
        for(i=1;i<=N;i++)//i的含义是考虑了i种物品 
        {
            for(j=data77[i][1];j<=F-E;j++)//从背包刚好能装下一个新物品,每次增加一个容量,直至题目要求体积
            {//这里j的含义是背包的容量
                if(dp[j]==-1&&dp[j-data77[i][1]]!=-1)dp[j]=dp[j-data77[i][1]]+data77[i][0];//注意这里判断条件与赋值语句的不同,不要漏掉data77[i][0] 
                else if(dp[j]!=-1&&dp[j-data77[i][1]]==-1)dp[j]=dp[j];
                else dp[j]=minhh(dp[j],dp[j-data77[i][1]]+data77[i][0]);
            }
        }
    //完全背包和01背包的区别就在于,01背包由放1个物品考虑到放n个物品,而完全背包由用一种物品填满考虑到用n种物品填满
    //,每种物品都考虑放0个直到填满
        if(dp[F-E]==-1)printf("This is impossible.\n");
        else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F-E]);
    }
    return 0;
}

总结

1.最重要的思想,完全背包和01背包的区别就在于,01背包由放1个物品考虑到放n个物品,而完全背包由用一种物品填满考虑到用n种物品填满

2.实现方式,用-1代表不可能,不是依次考虑放几个物品,而是依次考虑有n种物品选择时,依次考虑体积从刚好放得下一个第n种物品,到题目要求体积,每次加1而不是每次加一个第n种物品的体积是因为这里用一维数组进行存储,每一次遍历都要把上一组数据覆盖掉,如果不理解可以将一维数组展开成n维数组理解

上一篇:asm磁盘组磁盘替换实验


下一篇:阿里云云服务器产品周开启 云服务器1核2G秒杀38元/年