第k大值01背包问题
第k大值01背包问题
1944864971 发表于2年前
第k大值01背包问题
  • 发表于 2年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

http://acm.hdu.edu.cn/showproblem.php?pid=2639
/*
第一行输入t 代表t组测试数据
第二行 输入物品个数 背包容量 要求的第k大值
物品的价值
物品的重量

分析:
平常我们用的dp[j]=max(dp[j],dp[j-w[i]]+v[i]);所求的就是最大值 当然在1物品下容量为10的情况下有最大值 次大值
三大值 。。。。。。。。。。。。
很容易想到用dp[][k]二维数组 在当前的容量下第k大值的价值
*/

include

include

include

include

using namespace std;
int dp[1005][50],d1[50];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
int w[105],v[105];
memset(dp,0,sizeof(dp));
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=n; i++)
scanf("%d",&v[i]);
for(int i=1; i<=n; i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
{
int count=0;
for(int q=1;q<=k;q++)
{
d1[count++]=dp[j][q];//统统加入一个数组
d1[count++]=dp[j-w[i]][q]+v[i];
}
sort(d1,d1+count);//然后排序就是从最大值到第k大值了
int op=1;
for(int q=count-1;q>=0;q--)
{
if(op>k)break;
if(q==count-1||d1[q]!=d1[q+1])
dp[j][op++]=d1[q];//比如5 5 5 4 3 2 这里面有重复的值 第一个5和第二个5都是最大值 所以去重
}
}
printf("%d\n",dp[m][k]);
}

return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: