[HDU2546]饭卡<dp 01背包>

   链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546

#题目描述：

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

#输入

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。

#输出

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

#样例输入

1

50

5

10

1 2 3 2 1 1 2 3 2 1

50

0

#样例输出

-45

32

 思路：

典型的01背包类问题，将余额减去5，就是背包的容量，然后尽可能多的往里面装东西。因为可以负的，所以减去的5最后可以买下最贵的菜。

题就变成了，去除价格最高后剩下的物品，余额减去5的背包容量，使背包最后剩下的容量最小。

得出的这个结果加上5再减去最贵的菜就是答案。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3fffffff
using namespace std;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void fre(){
     freopen("     .in","r",stdin);
     freopen("     .out","w",stdout);
}

int n,val[1005],rest,dp[1005];

void sce_main(){
    for(int i=1;i<=n;i++){
        val[i]=read();
    }rest=read();
    sort(val+1,val+1+n);
    if(rest<5){
        cout<<rest<<endl;return ;
    }
    rest-=5;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n-1;i++){
        for(int j=rest;j>=val[i];j--){
            dp[j]=max(dp[j],dp[j-val[i]]+val[i]);
        }
    }
    cout<<rest-dp[rest]+5-val[n]<<endl;
}

int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)return 0;
        sce_main();        
    }
    return 0;
}

。。

很久没碰博客了，一直再说继续打ACM，但是也只是口号喊得响。

今天好不容易又开始做题

结果发现一道简简单单的01背包问题竟然有些做不来了

想要回到以前的水平

任重而道远啊。

不过真好，最近还是有个好朋友与我一起在努力。