济南建设网站,网站开发技术路线图,163企业邮箱登入口,建设网站就选用什么样的公司题目链接 这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下#xff0c;容量为j时能放物品的数量#xff08;这道题歌曲数量对应物品数量#xff0c;容量对应时间#xff09;。 技巧#xff08;收获#xff09; 二维dp数组可以视情况优化为一维dp数组…题目链接 这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下容量为j时能放物品的数量这道题歌曲数量对应物品数量容量对应时间。 技巧收获 二维dp数组可以视情况优化为一维dp数组。 在0-1背包问题的初始化中 背包必须装满dp[0] 0其他初始化为负无穷背包可以不装满dp全部初始化为0有关这一点的解释。在遍历时如果是找价值最大的从后往前遍历。 参考https://blog.csdn.net/pegasuswang_/article/details/9131619
#include stdio.h
#define jinge 678int max(int a, int b) {return a b ? a : b;
}int main() {int T, n, t;int i, j; scanf(%d, T);int song[51] {0};int dp[10000] {0};int count 1;while (T--) {scanf(%d %d, n, t);for (i 1; i n; i) {scanf(%d, song[i]);}for (i 0; i t; i) { dp[i] -1;}dp[0] 0;int ans 0,ans_time 0;for (i 1; i n; i) {for (j t-1; j song[i]; j--) {if(dp[j - song[i]] 1dp[j]){dp[j] dp[j - song[i]] 1;//这里的dp[j] dp[j - song[i]] 1;相当于dp[i][j] dp[i-1][j - song[i]] 1;}}}for(jt-1;j0;j--)if(dp[j]ans){ans dp[j];ans_time j;}for(int i0;it;i){printf(%3d ,dp[i]);}printf(Case %d: %d %d\n, count, ans 1, ans_time jinge);}return 0;
}/*
2
3 100
60 70 80
3 100
30 69 70
*/
