2023年8月1日发(作者：)

背包问题——⽆限物品的背包问题，0-1背包问题与劲歌⾦曲（uva12563）⽆限物品的背包问题物品⽆限的背包问题。有n种物品，每种均有⽆穷多个。第i种物品的体积为Vi，重量为Wi。选⼀些物品装到⼀个容量为C的背包中，使得背包内物品在总体积不超过C的前提下重量尽量⼤。1≤n≤1001≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106。测试数据：3 51 22 33 2answer:103 72 13 24 3answer:53 53 34 23 2answer:30解题思路dp思维：每个物品都可以⽆限使⽤，且我们不需要考虑能否完全利⽤背包的容量C，只要所装物品的重量总和最⼤即可。由于物品是⽆限使⽤的，所以在状态转移中我们所需要思考的是此时背包的容量，⽽不是对于⾯向物品思考状态。状态转移⽅程：i代表着背包的容积dp【i】=max（dp【i】，dp【i-v【j】】+w【j】）递归思维：相当于⼀个有向图的动态规划，我们对每个重量都探讨它接下可装物品的最⼤重量。递归：#include #include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))//由于物品⽆限且不需要如硬币问题⼀样必须装的恰到好处int d[M],C;int v[N],w[N];int dp(int C,int n){ int *ans=&d[C],i; //ans改变d【c】改变 if(*ans>0) return *ans; *ans=0; for(i=0;i=v[i]) *ans=Max(*ans,dp(C-v[i],n)+w[i]); return *ans;}int main(){ int n,ans,i; while(~scanf("%d%d",&n,&C)) { for(i=0;i#include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int main(){ int C,n; while(~scanf("%d%d",&n,&C)) { int i,j; int v[n],w[n]; int dp[M]={0}; //初始化为0 for(i=0;i=v[j]) dp[i]=Max(dp[i],dp[i-v[j]]+w[j]); printf("ans:%dn",dp[C]); } return 0;}01背包问题有n种物品，每种均只有1个。第i种物品的体积为Vi，重量为Wi。选⼀些物品装到⼀个容量为CC的背包中，使得背包内物品在总体积不超过C的前提下重量尽量⼤。1≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106。测试数据:5 6

1 22 43 44 5

5 6answer:10解题思路递归由于每个物品只能使⽤⼀次，所以我们需要标记，类似于DFS进⾏标记与恢复标记，再利⽤图的思维，对着不同体积，探讨它接下来体积所能装下物品重量的最⼤值#include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int flag[N]; //物品只能⽤⼀次需要标记类似dfsint n,v[N],w[N];int dp(int C) //为什么不加⼊记忆化？由于标记的存在并不适合记忆化.{ int ans=0,i; for(i=0;i=v[i]) { flag[i]=1; ans=Max(ans,dp(C-v[i])+w[i]); flag[i]=0; //恢复状态 } return ans;}int main(){ int C; while(~scanf("%d%d",&n,&C)) { int i; for(i=0;i#include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int dp[N][M];int main(){ int C,n,i,j,v[N],w[N]; while(~scanf("%d%d",&n,&C)) { for(i=1;i<=n;i++) //由于要预留dp【0】的位置 scanf("%d%d",&v[i],&w[i]); for(i=0;i=v[i]) dp[i][j]=Max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); else dp[i][j]=dp[i-1][j]; printf("%dn",dp[n][C]); } return 0;}我们发现每次dp只需要⽤到上⼀层的数组那么我们可以对dp数组进⾏优化，变成⼀维。注意：这⾥对容量C我们需要⾃顶向下，不然会出现dp改变了前⾯的数，dp【j-v【i】】+w【i】中的dp【j-v【i】】⽤的是改变后的数，不是我们所需要的保存上⼀层数组的数。#include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int main(){ int n,C,i,j; while(~scanf("%d%d",&n,&C)) { int dp[M]={0}; int v[N],w[N]; for(i=0;i=v[i];j--) //这⾥要⾃顶向下不然会出现dp【i】改变了前⾯的数导致后⾯的j-v【i】⽤的是改变后的数导致结果异常 dp[j]=Max(dp[j],dp[j-v[i]]+w[i]); printf("ans%dn",dp[C]); } return 0;}还可再进⾏⼀点简单的优化： for(i=0;i=v;j--)

dp[j]=Max(dp[j],dp[j-v]+w); }劲歌⾦曲(If you smiled when you see the title, this problem is for you

_)For those who don’t know KTV, see: /wiki/Karaoke_boxThere is one very popular song called Jin Ge Jin Qu(劲歌⾦曲). It is a mix of 37 songs, and isextremely long (11 minutes and 18 seconds) — I know that there are Jin Ge Jin Qu II and III, andsome other unofficial versions. But in this problem please forget about is it popular? Suppose you have only 15 seconds left (until your time is up), then you shouldselect another song as soon as possible, because the KTV will not crudely stop a song before it ends(people will get frustrated if it does so!). If you select a 2-minute song, you actually get 105 extraseconds! ….and if you select Jin Ge Jin Qu, you’ll get 663 extra secondsNow that you still have some time, but you’d like to make a plan now. You should stick to thefollowing rules: Don’t sing a song more than once (including Jin Ge Jin Qu). For each song of length t, either sing it for exactly t seconds, or don’t sing it at all. When a song is finished, always immediately start a new goal is simple: sing as many songs as possible, and leave KTV as late as possible (since wehave rule 3, this also maximizes the total lengths of all songs we sing) when there are he first line contains the number of test cases T (T ≤ 100). Each test case begins with two positiveintegers n, t (1 ≤ n ≤ 50, 1 ≤ t ≤ 109), the number of candidate songs (BESIDES Jin Ge Jin Qu)and the time left (in seconds). The next line contains n positive integers, the lengths of each song, inseconds. Each length will be less than 3 minutes — I know that most songs are longer than 3 don’t forget that we could manually “cut” the song after we feel satisfied, before the song ends. Sohere “length” actually means “length of the part that we want to sing”.It is guaranteed that the sum of lengths of all songs (including Jin Ge Jin Qu) will be strictly largerthan For each test case, print the maximum number of songs (including Jin Ge Jin Qu), and the total lengthsof songs that you’ll ation:In the first example, the best we can do is to sing the third song (80 seconds), then Jin Ge Jin Qufor another 678 the second example, we sing the first two (30+69=99 seconds). Then we still have one secondleft, so we can sing Jin Ge Jin Qu for extra 678 seconds. However, if we sing the first and third songinstead (30+70=100 seconds), the time is already up (since we only have 100 seconds in total), so wecan’t sing Jin Ge Jin Qu anymore!Universidad de Valladolid OJ: 12563 – Jin Ge Jin Qu hao 2/2Sample Input23 10060 70 803 10030 69 70Sample OutputCase 1: 2 758Case 2: 3 777题意：假如你的ktv还有15秒就时间到了，但是当你正在唱⼀⾸歌的时候他们并不会把你赶⾛⽽是会等该歌曲播完才让你离开，这时你可以点⼀⾸两分钟的歌，相当于你多唱了105秒。假如你正在ktv唱歌，还剩下t秒时间，你决定接下来只唱你最爱的n⾸歌，在时间结束之前你会再点⼀⾸《劲歌⾦曲》（时长678秒），求出你⼀共唱了⼏⾸歌和唱了多长时间。输⼊n（n<=50）,t(t<=10^9)和每⾸歌的长度（保证不超过三分钟）。解题思路单纯的思考所唱的时间最长，就是⼀个简单的01背包问题，边界有所不同是t-1（留⼀秒给劲歌⾦曲）。#include #include #define Max(a,b) ((a)>(b)?(a):(b))int main(){ int T,i,j; scanf("%d",&T); while(T--) { int n,t,time[50]; int *dp; scanf("%d%d",&n,&t); dp=(int *)calloc(t,sizeof(int)); //初始化为0 for(i=0;i=time[i];j--) dp[j]=Max(dp[j],dp[j-time[i]]+time[i]); printf("%dn",dp[t-1]+678); } return 0;}那么我们再加⼊⼀个歌曲数的观念，你会发现每次歌曲数增加都伴随着dp（歌唱时间）的增加，那么我们只要将歌曲数的状态⽅程放⼊循环中同dp⼀起增加即可。#include #include #define Max(a,b) ((a)>(b)?(a):(b))int main(){ int T,i,j; scanf("%d",&T); while(T--) { int n,t,time[50]; int *dp,*count; scanf("%d%d",&n,&t); dp=(int *)calloc(t,sizeof(int)); //初始化为0 count=(int *)calloc(t,sizeof(int)); for(i=0;i=time[i];j--) { count[j]=Max(count[j],count[j-time[i]]+1); dp[j]=Max(dp[j],dp[j-time[i]]+time[i]); } printf("%d %dn",count[t-1]+1,dp[t-1]+678); } return 0;}

2023年8月1日发(作者：)

背包问题——⽆限物品的背包问题，0-1背包问题与劲歌⾦曲（uva12563）⽆限物品的背包问题物品⽆限的背包问题。有n种物品，每种均有⽆穷多个。第i种物品的体积为Vi，重量为Wi。选⼀些物品装到⼀个容量为C的背包中，使得背包内物品在总体积不超过C的前提下重量尽量⼤。1≤n≤1001≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106。测试数据：3 51 22 33 2answer:103 72 13 24 3answer:53 53 34 23 2answer:30解题思路dp思维：每个物品都可以⽆限使⽤，且我们不需要考虑能否完全利⽤背包的容量C，只要所装物品的重量总和最⼤即可。由于物品是⽆限使⽤的，所以在状态转移中我们所需要思考的是此时背包的容量，⽽不是对于⾯向物品思考状态。状态转移⽅程：i代表着背包的容积dp【i】=max（dp【i】，dp【i-v【j】】+w【j】）递归思维：相当于⼀个有向图的动态规划，我们对每个重量都探讨它接下可装物品的最⼤重量。递归：#include #include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))//由于物品⽆限且不需要如硬币问题⼀样必须装的恰到好处int d[M],C;int v[N],w[N];int dp(int C,int n){ int *ans=&d[C],i; //ans改变d【c】改变 if(*ans>0) return *ans; *ans=0; for(i=0;i=v[i]) *ans=Max(*ans,dp(C-v[i],n)+w[i]); return *ans;}int main(){ int n,ans,i; while(~scanf("%d%d",&n,&C)) { for(i=0;i#include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int main(){ int C,n; while(~scanf("%d%d",&n,&C)) { int i,j; int v[n],w[n]; int dp[M]={0}; //初始化为0 for(i=0;i=v[j]) dp[i]=Max(dp[i],dp[i-v[j]]+w[j]); printf("ans:%dn",dp[C]); } return 0;}01背包问题有n种物品，每种均只有1个。第i种物品的体积为Vi，重量为Wi。选⼀些物品装到⼀个容量为CC的背包中，使得背包内物品在总体积不超过C的前提下重量尽量⼤。1≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106。测试数据:5 6

1 22 43 44 5

5 6answer:10解题思路递归由于每个物品只能使⽤⼀次，所以我们需要标记，类似于DFS进⾏标记与恢复标记，再利⽤图的思维，对着不同体积，探讨它接下来体积所能装下物品重量的最⼤值#include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int flag[N]; //物品只能⽤⼀次需要标记类似dfsint n,v[N],w[N];int dp(int C) //为什么不加⼊记忆化？由于标记的存在并不适合记忆化.{ int ans=0,i; for(i=0;i=v[i]) { flag[i]=1; ans=Max(ans,dp(C-v[i])+w[i]); flag[i]=0; //恢复状态 } return ans;}int main(){ int C; while(~scanf("%d%d",&n,&C)) { int i; for(i=0;i#include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int dp[N][M];int main(){ int C,n,i,j,v[N],w[N]; while(~scanf("%d%d",&n,&C)) { for(i=1;i<=n;i++) //由于要预留dp【0】的位置 scanf("%d%d",&v[i],&w[i]); for(i=0;i=v[i]) dp[i][j]=Max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); else dp[i][j]=dp[i-1][j]; printf("%dn",dp[n][C]); } return 0;}我们发现每次dp只需要⽤到上⼀层的数组那么我们可以对dp数组进⾏优化，变成⼀维。注意：这⾥对容量C我们需要⾃顶向下，不然会出现dp改变了前⾯的数，dp【j-v【i】】+w【i】中的dp【j-v【i】】⽤的是改变后的数，不是我们所需要的保存上⼀层数组的数。#include #include #define N 103#define M 100003#define Max(a,b) ((a)>(b)?(a):(b))int main(){ int n,C,i,j; while(~scanf("%d%d",&n,&C)) { int dp[M]={0}; int v[N],w[N]; for(i=0;i=v[i];j--) //这⾥要⾃顶向下不然会出现dp【i】改变了前⾯的数导致后⾯的j-v【i】⽤的是改变后的数导致结果异常 dp[j]=Max(dp[j],dp[j-v[i]]+w[i]); printf("ans%dn",dp[C]); } return 0;}还可再进⾏⼀点简单的优化： for(i=0;i=v;j--)

dp[j]=Max(dp[j],dp[j-v]+w); }劲歌⾦曲(If you smiled when you see the title, this problem is for you

_)For those who don’t know KTV, see: /wiki/Karaoke_boxThere is one very popular song called Jin Ge Jin Qu(劲歌⾦曲). It is a mix of 37 songs, and isextremely long (11 minutes and 18 seconds) — I know that there are Jin Ge Jin Qu II and III, andsome other unofficial versions. But in this problem please forget about is it popular? Suppose you have only 15 seconds left (until your time is up), then you shouldselect another song as soon as possible, because the KTV will not crudely stop a song before it ends(people will get frustrated if it does so!). If you select a 2-minute song, you actually get 105 extraseconds! ….and if you select Jin Ge Jin Qu, you’ll get 663 extra secondsNow that you still have some time, but you’d like to make a plan now. You should stick to thefollowing rules: Don’t sing a song more than once (including Jin Ge Jin Qu). For each song of length t, either sing it for exactly t seconds, or don’t sing it at all. When a song is finished, always immediately start a new goal is simple: sing as many songs as possible, and leave KTV as late as possible (since wehave rule 3, this also maximizes the total lengths of all songs we sing) when there are he first line contains the number of test cases T (T ≤ 100). Each test case begins with two positiveintegers n, t (1 ≤ n ≤ 50, 1 ≤ t ≤ 109), the number of candidate songs (BESIDES Jin Ge Jin Qu)and the time left (in seconds). The next line contains n positive integers, the lengths of each song, inseconds. Each length will be less than 3 minutes — I know that most songs are longer than 3 don’t forget that we could manually “cut” the song after we feel satisfied, before the song ends. Sohere “length” actually means “length of the part that we want to sing”.It is guaranteed that the sum of lengths of all songs (including Jin Ge Jin Qu) will be strictly largerthan For each test case, print the maximum number of songs (including Jin Ge Jin Qu), and the total lengthsof songs that you’ll ation:In the first example, the best we can do is to sing the third song (80 seconds), then Jin Ge Jin Qufor another 678 the second example, we sing the first two (30+69=99 seconds). Then we still have one secondleft, so we can sing Jin Ge Jin Qu for extra 678 seconds. However, if we sing the first and third songinstead (30+70=100 seconds), the time is already up (since we only have 100 seconds in total), so wecan’t sing Jin Ge Jin Qu anymore!Universidad de Valladolid OJ: 12563 – Jin Ge Jin Qu hao 2/2Sample Input23 10060 70 803 10030 69 70Sample OutputCase 1: 2 758Case 2: 3 777题意：假如你的ktv还有15秒就时间到了，但是当你正在唱⼀⾸歌的时候他们并不会把你赶⾛⽽是会等该歌曲播完才让你离开，这时你可以点⼀⾸两分钟的歌，相当于你多唱了105秒。假如你正在ktv唱歌，还剩下t秒时间，你决定接下来只唱你最爱的n⾸歌，在时间结束之前你会再点⼀⾸《劲歌⾦曲》（时长678秒），求出你⼀共唱了⼏⾸歌和唱了多长时间。输⼊n（n<=50）,t(t<=10^9)和每⾸歌的长度（保证不超过三分钟）。解题思路单纯的思考所唱的时间最长，就是⼀个简单的01背包问题，边界有所不同是t-1（留⼀秒给劲歌⾦曲）。#include #include #define Max(a,b) ((a)>(b)?(a):(b))int main(){ int T,i,j; scanf("%d",&T); while(T--) { int n,t,time[50]; int *dp; scanf("%d%d",&n,&t); dp=(int *)calloc(t,sizeof(int)); //初始化为0 for(i=0;i=time[i];j--) dp[j]=Max(dp[j],dp[j-time[i]]+time[i]); printf("%dn",dp[t-1]+678); } return 0;}那么我们再加⼊⼀个歌曲数的观念，你会发现每次歌曲数增加都伴随着dp（歌唱时间）的增加，那么我们只要将歌曲数的状态⽅程放⼊循环中同dp⼀起增加即可。#include #include #define Max(a,b) ((a)>(b)?(a):(b))int main(){ int T,i,j; scanf("%d",&T); while(T--) { int n,t,time[50]; int *dp,*count; scanf("%d%d",&n,&t); dp=(int *)calloc(t,sizeof(int)); //初始化为0 count=(int *)calloc(t,sizeof(int)); for(i=0;i=time[i];j--) { count[j]=Max(count[j],count[j-time[i]]+1); dp[j]=Max(dp[j],dp[j-time[i]]+time[i]); } printf("%d %dn",count[t-1]+1,dp[t-1]+678); } return 0;}