hdu1248 寒冰王座 完全背包以及其它做法

下面的题是一个完全背包 当然用别的方法也能做

寒冰王座

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)
TotalSubmission(s):5723AcceptedSubmission(s):2804

ProblemDescription

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:"我要买道具!"

地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."

死亡骑士:"好的,给我一个血瓶."

说完他掏出那张N元的大钞递给地精商人.

地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."

死亡骑士:"......"

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.

现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.

Input

输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.

注意:地精商店只有题中描述的三种道具.

Output

对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.

SampleInput

2900250

SampleOutput

050

这是一个完全背包问题我们可以把完全背包问题变成我们已经熟悉的01背包问题现在我们已经知道只有3种物品我们可以假设3中物品的体积分别为150200350而其对应的价值分别为也分别为150200350现在我们已经转化为01背包问题

#include<stdio.h>

#include<string.h>

intdp[10001];

inttool[4]={0,150,200,350};

intmain()

{

intt,n,i,j;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

memset(dp,0,sizeofdp);

for(i=1;i<=3;i++)//和01背包问题一样这里其实指的是种类数即该种类存不存在要不要会出现哪种结果然后比较两者的大小

for(j=tool[i];j<=n;j++)

dp[j]=dp[j]>dp[j-tool[i]]+tool[i]?dp[j]:dp[j-tool[i]]+tool[i];

printf("%d\n",n-dp[n]);

}

return0;

}

讲解

注意这句话for(j=tool[i];j<=n;j++)我们已经不是每个物品只选一次了所以就不用按从v到tool[i]的顺序来了

首先想想为什么0-1背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

继续列个表给大家看看：假设包体积为800

j------->

iValv12。。。150.。。。。。200.。。。。。。300。。。350.。。。。。800

↓15015000。。。。150。。。。。150.。。。。。。300.。。300.。。。。。750

20020000.。。。150.。。。。。200.。。。。。。300.。。350.。。

350 350 00 000 00略 略 略

对于f[j]=max{f[j],f[j-c[i]]+w[i]};

我们可以看出当i=1的时候可以求出<=n的任何体积时的最优值

当i=2时我们可以比较前一次得到的f[j]和加入新物品后产生的f[j]哪个更大取出大个这时候就能得出有2个物品的时候的最优解类似当i=3我们就能求出来当有3个物品时的最优解

而在01背包中等号右边的f[j]是上一层的即当i=2时而f[j]是上一层的结果然后和上一层的f[v-c[i]]加上新加入物品的对应值比较大小取大的赋给新的就是i=2层的f[i]

此问题中是从bool[i]到n的所以等号右边的f[i]可以是本层的所以对于一个物品可以重复加

————————————————————————————————————————————————————————————

献上一个非背包做法 我自己的

这种发放就是暴力出所有的不给小费的情况 最多就200个 所以不会超时

可以发现350 以后只要是 50的倍数 就会付0小费 所以 我们也可以把我下面复杂的暴力过程去掉 然后就不要我说了吧

#include<stdio.h>
struct haha
{
int num;
int flag;
}a[10002];
int main()
{
int i,j,k,t,n,b[202];
scanf("%d",&t);
for(i=0;i<=10000;i++)
{
a[i].num=i;
a[i].flag=0;
}
j=0;
for(i=150;i<=10000;i+=50)
if(i%150==0||i%200==0||i%350==0)
{
a[i].flag=1;
b[j++]=i;
}
for(i=0;i<j;i++)
for(k=0;k<j;k++)
{
if(b[i]+b[k]<=10000)
{
a[b[i]+b[k]].flag=1;
}
}
j=0;
for(i=0;i<=10000;i++)
if(a[i].flag==1)
b[j++]=a[i].num;
while(t--)
{
scanf("%d",&n);
i=0;
for(i=0;i<j;i++)
{
if(n<150) {printf("%d\n",n);break;}
if(n<=b[i])
{
if(n==b[i]) printf("0\n");
else printf("%d\n",n-b[i-1]);
break;
}
}
}
return 0;
}

去掉暴力过程后 ：

1 #include<stdio.h>
2 main()
3 {
4 int list[6]={0,50,100,0,0,50};
5 int t,n;
6 scanf("%d",&t);
7 while(t--)
8 {
9 scanf("%d",&n);
10 if(n<300)
11 printf("%d\n",n%50+list[n/50]);
12 else
13 printf("%d\n",n%50);
14 }
15 }