HDOJ 1248 寒冰王座 (完全背包) - c++编程基础

题意：用面额为N的钞票能买到商品，因为店铺不找零，所以求“浪费”的最小金额。
思路：这道题是一道典型的完全背包题（也可以用别的方法解），将150，200，350作为物体体积，N做为背包容积。
[cpp]
#include
#include

#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]=w[j-type[i]]+type[i];
}
}
printf("%d\n",n-w[n]);
}
}
return 0;
}

作者：sdc1992