HDOJ 1248 寒冰王座 (完全背包)

題意：用面額為N的鈔票能買到商品，因為店鋪不找零，所以求“浪費”的最小金額。
思路：這道題是一道典型的完全背包題（也可以用別的方法解），將150，200，350作為物體體積，N做為背包容積。
[cpp] 
#include<stdio.h> 
#include<string.h> 
 
#define N 11111 
 
int type[4]={0,150,200,350},w[N]; 
 
int main() 
{ 
    int t,n,i,j; 
    while(scanf("%d",&t)==1) 
    { 
        while(t--) 
        { 
            scanf("%d",&n); 
            memset(w,0,sizeof(w)); 
            for(i=1;i<=3;i++)//表示該種物品有或沒有（01背包） 
            { 
        for(j=type[i];j<=n;j++)//注意：此處與01背包不同，原因請查閱《背包九講》（第二版） 
                { 
                    if(w[j]<w[j-type[i]]+type[i]) 
                        w[j]=w[j-type[i]]+type[i]; 
                } 
            } 
            printf("%d\n",n-w[n]); 
        } 
    } 
    return 0; 
} 

作者：sdc1992