Problem Description
The title of this problem is familiar,isn't it?yeah,if you had took part in the "Rookie Cup" competition,you must have seem this title.If you haven't seen it before,it doesn't matter,I will give you a link:
Here is the link:
http://acm.hdu.edu.cn/showproblem.php?pid=2602
Today we are not desiring the maximum value of bones,but the K-th maximum value of the bones.NOTICE that,we considerate two ways that get the same value of bones are the same.That means,it will be a strictly decreasing sequence from the 1st maximum , 2nd maximum
.. to the K-th maximum.
If the total number of different values is less than K,just ouput 0.
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, K(N <= 100 , V <= 1000 , K <= 30)representing the number of bones and the volume of his bag and the K we need. And the second line contain N integers representing the value
of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the K-th maximum of the total value (this number will be less than 231).
Sample Input
3
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
1 2 3 4 5
5 4 3 2 1
5 10 16
1 2 3 4 5
5 4 3 2 1
Sample Output
12
2
0
第K优解问题
其基本思想是将每个状态都表示成有序队列,将状态转移方程中的max/min转化成有序队列的合并。如果要求第K优解,那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时,第k优解的值。 显然f[i][v] [1..K]这K个数是由大到小排列的,所以我们把它认为是一个有序队列。
然后原方程就可以解释为:f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列 f[i-1][v]即f[i-1][v][1..K],f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N] [V][K]。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int bag[1000+10][55],val[101],n,v,k,vol[102],used[1000+10],a[55],b[55];
void _01bag()
{
int i,j,t,x,y,z;
memset(used,0,sizeof(used));
memset(bag,0,sizeof(bag));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=0;i<n;i++)
for(j=v;j>=vol[i];j--)
{
for(t=1;t<=k;t++)
{
a[t]=bag[j][t];
b[t]=bag[j-vol[i]][t]+val[i];
}
x=y=z=1;
while(z<=k&&(x<=k||y<=k))
{
if(a[x]>=b[y])
{
bag[j][z]=a[x]; x++;
}
else
{
bag[j][z]=b[y];y++;
}
if(bag[j][z]!=bag[j][z-1]) z++;
}
}
printf("%d\n",bag[v][k]);
}
int main()
{
int i,cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d %d %d",&n,&v,&k);
for(i=0;i<n;i++)
scanf("%d",&val[i]);
for(i=0;i<n;i++)
scanf("%d",&vol[i]);
_01bag();
}
return 0;
}
参考了宇宙吾心
分享到:
相关推荐
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
HDU2013暑期多校联合训练第一场0723-解题报告和标程
搜索 dfs 解题代码 hdu1241
2017hdu多校联合训练第一场标程及数据
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码