程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ 2546 飯卡 (01背包)

HDOJ 2546 飯卡 (01背包)

編輯:C++入門知識

題意:卡內有m元錢,有n種菜可以買(每種菜只可以買一次),只要卡內金額大於等於5元就可以買任何菜(刷到負也可以)。求最少可使卡上的余額為多少。
思路:最貴的一個菜一定是最後買,然後用01背包求(m-5)元錢可買的菜的最大金額,然後(m-最大金額-最貴的菜的價錢)即為所求。
[cpp] 
#include<stdio.h> 
#include<string.h> 
 
#define maxn 1111 
 
int val[maxn],f[maxn]; 
 
main() 

    int n,m,i,j,max,pos; 
    while(scanf("%d",&n)&&n) 
    { 
        for(i=1;i<=n;i++) 
            scanf("%d",&val[i]); 
        scanf("%d",&m); 
        if(m<5) 
        { 
            printf("%d\n",m); 
            continue; 
        } 
        for(max=-1,pos=0,i=1;i<=n;i++) 
            if(max<val[i]) 
            { 
                max=val[i]; 
                pos=i; 
            } 
        memset(f,0,sizeof(f)); 
        for(i=1;i<=n;i++) 
        { 
            if(pos==i) 
                continue;  www.2cto.com
            for(j=m-5;j>=val[i];j--) 
                if(f[j]<f[j-val[i]]+val[i]) 
                    f[j]=f[j-val[i]]+val[i]; 
        } 
        printf("%d\n",m-f[m-5]-max); 
    } 
    return 0; 

作者:sdc1992

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved