杭店 ACM 1864 最大报销额 01背包

![勾选C++才能过
题意：
先规定可以报销一定额度的发票，物品类型有A，B，C，三种。要求每张发票总额不得超过1000元，单项物品不得超过600.求报销的最大额
分析：
先找到合格的发票，然后再挑选总额最大的几张发票（01背包来解决）

如何找出合格发票？
1.发票中只有ABC着三种物品
2.单张发票的额度<=1000.
3.一张发票中，单项物品总额<=600

题目中的价钱都是浮点数，01背包只能处理整数，怎么办？
题目给的数据最多两位数（题目没说保留几位小数），所以我们可以把数据都*100，等用01背包的方法计算完后，再强值转换成浮点数。

01背包？
扩展：
有N种物品（每种物品只有一个）和一个容量为V的背包。第i件物品的占用空间是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路：
每种物品仅有一件，只有两种选择：放或不放。用子问题定义状态：即dp[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

code:
for(int i = 1; i <= n; i++) { for(int j = 0; j <= W; j++) { if(j < w[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); } }
本题：
将每一张发票当作是一种物品，同样只有两种选择：要或不要，总额度相当于背包容量
注意确保数组够大，1000*100*35

#include<stdio.h>

#include<string.h>

#define max(a,b) (a>b)?a:b

int dp[3500000],N[35];

int main()

{

    int cot,Val,A,B,C,n,i,j,k,flag;

    double val,price;

    while(scanf("%lf %d",&val,&cot)!=EOF&&cot)

    {

         k=0;

        char ABC;

        memset(dp,0,sizeof(dp));

        Val=(int)(val*100);

        while(cot--)

        {

            scanf("%d",&n);

            A=0;

            B=0;

            C=0;

            flag=1;

            while(n--)

            {

                scanf(" %c:%lf",&ABC,&price);

                j=(int)(price*100);

                if(ABC=='A')

                    A+=j;

                else if(ABC=='B')

                    B+=j;

                else if(ABC=='C')

                    C+=j;

                else

                {

                    flag=0;

                }

            }

                if(flag&&A<=60000&&B<=60000&&C<=60000&&A+B+C<=100000)

                {

                    N[k++]=A+B+C;

                }

            }

            for(i=0;i<k;i++)

                for(j=Val;j>=N[i];j--)

                {

                    dp[j]=max(dp[j],dp[j-N[i]]+N[i]);

                }

                printf("%.2lf\n",(double)dp[Val]/100.0);

    }

}

](https://img-blog.csdn.net/2018080513081644?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDQ3Mg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)

巴特西

杭店 ACM 1864 最大报销额 01背包

最新文章

热门文章