讨论 / 好不容易才找到真正求解背包问题第k优解的程序
飞雪天涯 2011-10-16 21:18:00
点我顶贴 收藏 删除
终于AC了,5555555555555

我好不容易才找到真正求解背包问题第k优解的程序!

dp[0][1]=0;

for (int i=1;i<=n;i++){

int weight,value;

cin>>weight>>value;

for (int j=v;j>=weight;j--)

if (dp[j-weight][1]>=0){

int pos1=1,pos2=1;

for (int people=1;people<=k;people++){

queue1[people]=dp[j-weight][people]+value;//队列1

queue2[people]=dp[j][people];//队列2

if (queue2[pos1]>=queue1[pos2]) dp[j][people]=queue2[pos1++];

else dp[j][people]=queue1[pos2++];

//类归并排序方法

}

}

}

#1 飞雪天涯@2008-10-26 08:11:00
回复 删除
早想到了……就是8会编!
#2 飞雪天涯@2008-10-26 08:26:00
回复 删除
[color=red]热烈的贺![/color][color=blue]123题![/color]
#3 飞雪天涯@2008-10-26 08:27:00
回复 删除
正好我的第123AC题是[color=blue]pid123[/color]
#4 libojie@2008-10-26 09:36:00
回复 删除
若第N个AC的题恰好是第N号题,那么称这个题为AC的一个不动点。我们可以计算AC N个题,共M个题的情况下有P个不动点的概率。

这是一个数学问题,同时是一个信息学编程问题……

#5 cc@2008-10-26 16:16:00
回复 删除
关于博弈中的ac是说 ,你ac了n个题,这n个题都是你懒得ac的 ,那么剩下的m个题中必然有p个题你仍然懒得ac,所以你还可以迅速ac掉…个题,这必然使rq下降,导致你能ac的题数目下降从而进一步导致noip的失利,所以,懒得ac的题多不一定是最优策略…… cc
#6 lijiaming12340@2011-10-16 21:18:00
回复 删除
全是大牛呀!
查看更多回复
提交回复