本文共 844 字，大约阅读时间需要 2 分钟。

饭卡 hdu2546

标签：01背包

/*    题意：只要剩余的钱不低于5元，就可以购买任何一种菜，          所以在使用01背包之前，我们首先要在现在所拥有的余额中保留5元，最后用这5元去购买最贵的物品，          而剩下的钱可以随意使用，也就是背包的总容量。*/#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 1005;int dish[maxn], dp[maxn];int main(){    int n, m;    while(scanf("%d", &n) && n)    {        for(int i = 0; i < n; i++)  scanf("%d", &dish[i]);        scanf("%d", &m);        if(m < 5)  {
  printf("%d\n", m);  continue;}        m -= 5;        sort(dish, dish + n);        memset(dp, 0, sizeof(dp));  //ZeroOnePack template        for(int i = 0; i < n - 1; i++)  //把最贵的菜保留            for(int j = m; j >= dish[i]; j--)                dp[j] = max(dp[j], dp[j - dish[i]] + dish[i]);  //"value", "volume"都是菜的价格        printf("%d\n", m + 5 - dish[n - 1] - dp[m]);  //m + 5 - dish[n - 1](买最贵的菜)    }    return 0;}
     
    
   

转载地址：http://rnkxi.baihongyu.com/