本文主要是介绍hud Watch The Movie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天写了一道二维背包问题；下面转强大的牛人的一大段话。
问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有 一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和 b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
算法
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
物品总个数的限制
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数 ”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物 品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
复数域上的背包问题
另一种看待二维背包问题的思路是：将它看待成复数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复 数。而常见的一维背包问题则是实数域上的背包问题。（注意：上面的话其实不严谨，因为事实上我们处理的都只是整数而已。）所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。
作为这种思想的练习，你可以尝试将P11中提到的“子集和问题”扩展到复数域（即二维），并试图用同样的复杂度解决。
小结
当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。
初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么 任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
我的
{ 这个问题中叔叔买m部电影给duoduo看，而且要求duoduo要看完，否则价值为0，所以此处的背包的m轴向必须装满，所以sum【k】【0】=0；而其他的值赋值为负无穷，
如果不能满足加上value【i】为第k部电影且前面k-1都装满电影，则为负值。
}
#include<string>
using namespace std;
int time_table[150],value[150],sum[1050][110];
int n,m,l;
void twodemenpack()
{
for(int i=1;i<=n;i++)
for(int k=l;k>=time_table[i];k--)
for(int j=m;j>=1;j--)
if(time_table[i]<=l)
sum[k][j]=max(sum[k][j],sum[k-time_table[i]][j-1]+value[i]);
}
int main()
{ int t;
const int N=999999;
cin>>t;
for(int i=0;i<t;i++)
{ cin>>n>>m>>l;
for(int k=1;k<=n;k++)
cin>>time_table[k]>>value[k];
for(int i=0;i<=l;i++)
for(int k=0;k<=m;k++)
if(k==0)
sum[i][k]=0;
else sum[i][k]=-N;
twodemenpack();
if(sum[l][m]<0)
cout<<"0"<<endl;
else
cout<<sum[l][m]<<endl;
}
return 0;
}
这篇关于hud Watch The Movie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
