这题 算很新颖的.....

以前 做01背包的时候 自己怎么没想到可以去求第K优解呢 就知道傻傻地直接写个dp[vol]直接求出能达到的最优解就是了=-=

一开始 我忽略了一点 dp[x] 1-vol 存的都是当前X体积下能存到的最优解... 所以 我要是选择遍历这个数组 来求出第K个解 肯定是不行的

因为 可能它不是在当前X下的最优决策 已经被更新 另外的策略代替了

然后 我百度了下 看到了提示

求次优解、第K优解
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。
其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然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]。总的复杂度是O(NVK)。
为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。
另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的
 

这里 进行合并的时候 让我想起了 归并排序..虽然归并用到了递归 不断地划分 但合并的思想是一样的
然后 我现在还存留的疑问是  如果将策略不同权值相同的两个方案看成是不同的解 代码应该如何修改
我自己 尝试了下 经验证 是错误的=-= 明明自己觉得能说服自己 -.-

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 const int size = 110; 6 int weight[size]; 7 int value[size]; 8 int dp[size*10][40]; 9 int pre[40];10 int next[40];11 12 int main()13 {14     int t , n , m , k , ans , cnt;15     int x , y , z;16     cin >> t;17     while(t--)18     {19         cin >> n >> m >> k;20         cnt = ans = 0;21         memset( dp , 0 , sizeof(dp) );22         for( int i = 0 ; i<n ; i++ )23             cin >> value[i];24         for( int i = 0 ; i<n ; i++ )25             cin >> weight[i];26         for( int i = 0 ; i<n ; i++ )27         {28             for( int j = m ; j>=weight[i] ; j-- )29             {30                 for( int f = 1 ; f<=k ; f++ )31                 {32                     pre[f] = dp[j][f];33                     next[f] = dp[ j-weight[i] ][f] + value[i];34                 }35                 x = y = z = 1;36                 next[k+1] = pre[k+1] = -1;37                 while( z<=k && (x<=k || y<=k) )38                 {39                     if( pre[x]>next[y] )40                     {41                         dp[j][z] = pre[x++];42                     }43                     else44                     {45                         dp[j][z] = next[y++];46                     }47                     if( dp[j][z] != dp[j][z-1] )48                         z ++;49                 }50             }51         }    52         cout << dp[m][k] << endl;53     }54     return 0;55 }

View Code

这里 要注意下  不能忘记了 next[k+1] = pre[k+1] = -1;这句话 因为可能next数组所有的K个元素都已经遍历完了 但dp[j][z]我们还没有选出K个解同时
pre[y]数组还在进行遍历 那么如果我们不讲它的next[k+1]置为-1的话 它就是个随机值 会很大 导致最终结果的错误.
同时 如果next pre数组都遍历完了 那么就直接退出循环 即使dp[j][z]数组的z还是<k那就还是用起初的0保存

 1                     if( pre[x]>next[y] ) 2                     { 3                         dp[j][z++] = pre[x++]; 4                     } 5                     else 6                     { 7                         dp[j][z++] = next[y++]; 8                     } 9                     //if( dp[j][z] != dp[j][z-1] )10                     //    z ++;

对于 刚刚提过的 策略不同权值相同算2个方案 我本来就这样修改了下 测了下 是错的
哪位 可以帮我解决下 我想这 对于理解背包思想 有很大的帮助 3Q .

hdu--2639--01背包第K解<不同决策的不同解法>