01 가방 의 응용 - 항 저 우 전기 2546

식사 카드
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15932 Accepted Submission(s): 5518
Problem Description
전자 과 본부 식당 의 식사 카드 는 구 매 하기 전에 잔액 을 판단 하 는 기괴 한 디자인 이 있다.한 상품 을 구 매 하기 전에 카드 에 남 은 금액 이 5 위안 보다 크 거나 같 으 면 반드시 구 매 에 성공 할 수 있다 (구 매 후 카드 잔액 이 마이너스 라 하 더 라 도). 그렇지 않 으 면 구 매 할 수 없다 (금액 이 충분 하 더 라 도).그래서 모두 가 가능 한 한 카드 의 잔액 을 최소 화하 기 를 바란다.어느 날 식당 에서 n 가지 채 소 를 팔 았 는데, 한 가지 채 소 를 한 번 씩 살 수 있 었 다.각 요리 의 가격 과 카드 의 잔액 을 알 고 있 으 니 최소한 카드 의 잔액 이 얼마 인지 물 어보 세 요.

Input
다 중 데이터.각 조 의 데이터: 첫 번 째 행 위 는 정수 n 으로 요리 의 수량 을 나타 낸다.n<=1000。 두 번 째 줄 은 n 개의 정 수 를 포함 하여 모든 채소 의 가격 을 나타 낸다.가격 이 50 을 넘 지 않 습 니 다.세 번 째 줄 은 정수 m 를 포함 하여 카드 의 잔액 을 나타 낸다.m<=1000。 n = 0 은 데이터 가 끝 났 음 을 나타 낸다.

Output
각 그룹의 입력 에 대해 한 줄 을 출력 하고 하나의 정 수 를 포함 하 며 카드 에 있 을 수 있 는 최소 잔액 을 표시 합 니 다.

Sample Input

 
    
    1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

Sample Output

 
   
     -45 32

其实这道题就是典型的01背包应用。但是是有条件的，就是那个5元的限制，余额必须>=5才能买菜。那么我们要是想要最终的余额最少，那么我可以用尽量接近5元的钱去买最贵的菜？？那这等同于把最贵的菜和5元拿出来，用剩下的菜填剩下的钱，然后用填完的剩下钱加上5减去最贵的菜的价格吗？答案是的。那我们来简单分析一下：定义一个变量remain=m-5；最贵的菜为max，那我们用剩下的菜去填remain。如果remain被全部填完，那毫无疑问5-max就是最小的余额。如果remain没有被填完，假设存在一个菜x，当用max去填remain时使5+remain-x最小，那么我们不一开始用x去填remain这样使剩下的钱会更小，那当remain+5-max会使余额更小。

分析完了就可以整理思路，把最大的菜挑出来，用剩下的菜去填remain，这就是01背包问题，使remaim尽可能被填完，那用剩下的钱+5-max就是所求值;

AC代码如下（必要的细节有相应注释说明）：

#include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    #define max(a,b) (a)>(b)?(a):(b)
    const int MAX=1000+5;

    int n,m;
    int price[MAX],dp[MAX];

    int main()
    {
    //    freopen("s","r",stdin);

        while(scanf("%d",&n)!=EOF)
        {
            if(!n)  {break;}

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

            int sum=0;

            for(int i=0;i=0;j--)
                        if(j>=price[i])
                           dp[j]=max(dp[j],dp[j-price[i]]+price[i]);//01          
                }

                printf("%d
",5+remain-dp[remain]-price[n-1]);
            }
        }
        return 0;
    }

01 가방 의 응용 - 항 저 우 전기 2546

좋은 웹페이지 즐겨찾기