Description

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑能帮他计算一下,最少他要给地精商人多少小费.

Input

输入一个N（1<=N<=10000）, N代表死亡骑士手中钞票的面值.
注意:地精商店只有题中描述的三种道具.

Output

请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.

Sample Input


900
Sample Output


0
Hint

如果不买或不够买则全部作为小费......

Source

/*  HELLO.C -- Hello, world */

#include "stdio.h"
#include "conio.h"

int main()
{

int i,j,k,n;
int sum=0,max=0;
scanf("%d",&n);
if(1<=n&&n<=10000)
{
for(i=0;i<=66;i++)
for(j=0;j<=50;j++)
for(k=0;j<=27;k++)
{
sum=(150*i)+(200*j)+(350*k);
if(sum<=n)
{

if(sum>=max)max=sum;
}
}
}


printf("%d\n",n-max);
getch();
return 0;
}


改了几次.......就不 知对不..........我等到快睡还没 得到答案   伟大的 WIN TC

[ 本帖最后由 A13433758072 于 2011-9-3 20:21 编辑 ]

貌似不对啊。。。。

楼主喜欢魔兽啊

有才。。。。。。。

完全背包
#include <stdio.h>
#include <string.h>
#define MAX( a , b ) ( a ) > ( b ) ? ( a ) : ( b )
const int map[3] = { 150 , 200 , 350 } ;
int dp[10001] ;
int main()
{
    int Total , n , i , j , max ;
    scanf("%d", &Total ) ;
    while( Total-- )
    {
        memset( dp , 0 , sizeof( dp ) ) ;
        max = 0 ;
        scanf("%d", &n ) ;
        for( j = 0 ; j < 3 ; ++j )
        {
            for( i = 0 ; i <= n ; ++i )
            {
                if( i >= map[j] )
                    dp[i] = MAX( dp[i] , dp[i - map[j]] + map[j] ) ;
                if( dp[i] > max )
                    max = dp[i] ;
            }
        }
        printf("%d\n", n - max ) ;
    }
    return 0 ;
}

这题用背包模型没有错，网上到处是这题的解题报告。不过由于题目的特殊性，可以有更简单的算法，复杂度为O(1)，绝对原创。
杭电1248题和你的题目几乎一样，只是输入格式不同，下面是按你的输入要求写的代码。

#include<stdio.h>
int cal(int n)
{
    int q, r;
    q = n / 150;
    r = n % 150;
    if(q * 50 < r)
        r -= q * 50;
    else
        r %= 50;
    return r;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", cal(n));
    return 0;
}

#include"stdio.h"

void main()
{
    int tip(int );
    int N,fee;
    printf("Please input one int number(0~10000):");
    scanf("%d",&N);
    fee = tip(N); //求小费
    printf("The fee is %d\n",fee);
}

int tip(int N)
{
    int i,j,k,p,sp;
    int min = N;
    for(i=0;i<=N/350;i++)
        for(j=0;j<=N/200;j++)
            for(k=0;k<=N/150;k++)
            {
                p = N-350*i-200*j-150*k;
                if(p>=0)
                {
                    sp = p;
                    if(sp<min)
                    {
                        min = sp;
                    }
                }
            }
    return min;//返回最少小费
}

[ 本帖最后由 不是不可能 于 2011-9-3 22:08 编辑 ]

补充一点在tip函数中三个循环中间加等号（例i<=N/350），p>=0这个地方也少个等号

#include<stdio.h>
void main()
{
    int i=0,j,p,m,left;
    int x,y,z,a[1000];
    printf("输入的钱数为：");
    scanf("%d",&m);
    for(x=0;x<=m/150;x++)
        for(y=0;y<=m/250;y++)
            for(z=0;z<=m/350;z++)
            {
                a[i]=m-150*x-200*y-350*z;
                i++;
            }
    j=i;
    p=a[0];
    for(i=0;i<=j;i++)
    {
        if((p>=a[i])&&(a[i]>=0)) p=a[i];
    }
    printf("所给的小费最少为：%d\n",p);
}