本文主要是介绍Jin Ge Jin Qu hao UVA - 12563 （0-1背包变形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
题目大意：某人在KTV唱歌，他一共剩余t秒的时间，例如：在还有15秒时再唱一首2分钟的歌，则实际上是多唱了105秒。他一定会在最后唱《Jin Ge Jin Qu》时长678秒，当然是在还有剩余时间的时候开始唱的。
在剩余的t秒里，他有n首自己喜欢的歌要唱，给出n首歌的时长。问要使得唱的曲目尽量的多，且多唱的时间尽量的多是多少；具体题意看链接或紫书。
输出唱的曲目数和唱的时间数。
ps:此题是紫书p274的例题，这是一个0-1背包的变形，可以把剩余的t秒当成背包，然后价值和重量都是n首歌的时长。
不同的是这里要求了两个条件，把这两个条件都当做dp的一部分，因为有优先条件，所以也就和简单的背包一样了。
这个题的一个坑点是给出t的范围是t<=1000000000，显然是开不下这个数组的，可是他又说每首歌的时长不超过3分钟，也就是t最大为50*180+678，完全是障眼法
#include <iostream>
#include <bits/stdc++.h>using namespace std;int v[100];
struct node
{int k;int time;
} dp[10000];
int main()
{int t,w=0;scanf("%d",&t);while(t--){int n,V;scanf("%d%d",&n,&V);int num=0;for(int i=1; i<=n; i++){scanf("%d",&v[i]);num+=v[i];}memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++){for(int j=V; j>v[i]; j--){node temp;temp.k=dp[j-v[i]].k+1;temp.time=dp[j-v[i]].time+v[i];if((temp.k>dp[j].k)||(temp.k==dp[j].k&&temp.time>dp[j].time)){dp[j]=temp;}}}//cout<<dp[V]<<endl;printf("Case %d: %d %d\n",++w,dp[V].k+1,dp[V].time+678);}return 0;
}
这篇关于Jin Ge Jin Qu hao UVA - 12563 （0-1背包变形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
