讨论 / 怎么做?????
wwww 2011-11-06 06:29:00
点我顶贴 收藏 删除
RT
#1 peterjiang@2008-09-29 05:45:00
回复 删除
动态规划+贪心
#2 飞雪天涯@2008-10-26 07:38:00
回复 删除
就是求前k优解(详见dd_engi的背包问题九讲)。
#3 飞雪天涯@2008-10-26 08:04:00
回复 删除
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++];

//类归并排序方法

}

}

}

#4 woai9bansc@2011-11-06 06:29:00
回复 删除
回复 地毯飞雪天涯 的帖子

二分答案+贪心验证

查看更多回复
提交回复