2546 ACM 01背包

題目http://acm.hdu.edu.cn/showproblem.php?pid=2546

思路：再01背包的問題上稍作修改

如何滿足 ：卡上的剩餘金額大于或等于5元，就一定可以購買成功（即使購買後卡上餘額為負），否則無法購買（即使金額足夠）？并使得餘額最少？

找到最貴的菜，卡上的剩餘金額大于或等于5元，必然要買下它，先讓容量-5再進入01背包循環，找到dp[容量-5](存的是該容量下，最大的價值）。

用了swap函數來找最貴的菜，是以用的C++頭檔案。

這是回家耍了6天後的第一個ACM題目，故意找的一個稍微熟悉又不白癡的算法，好久沒一次過，開心。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

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

int main()
{
    int n,cost[],weight[],va,v,dp[];
    while(scanf("%d",&n)!=EOF&&n!=)
    {
        for(int i=;i<n;i++)
        {
            scanf("%d",&cost[i]);
            if(cost[i]>cost[])
                swap(cost[i],cost[]);
            weight[i]=cost[i];
        }
        scanf("%d",&va);
        if(va<)
            printf("%d\n",va);
        else
        {
            v=va-;
            memset(dp,,sizeof(dp));
            for(int i=;i<n;i++)
            for(int j=v;j>=weight[i];j--)
                dp[j]=max(dp[j],dp[j-weight[i]]+cost[i]);
            printf("%d\n",va-dp[v]-cost[]);
        }

    }
}