解题思路:
注意事项:
参考代码:
/*装箱问题。有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30), 每个物品有一个体积 (正整数)。要求从 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 * 输入: 第一行,一个整数,表示箱子容量; 第二行,一个整数,表示有n个物品; 接下来n行,分别表示这n个物品的各自体积。 * 输出: 一个整数,表示箱子剩余空间。 */ #include<stdio.h> #define Max(a,b) a>b?a:b; int dp[32][19999] = { 0 }; int main() { int v = 0; int wu[32] = { 0 }; int i = 0; int f = 0; int j = 0; int n = 0; f = scanf("%d%d", &v, &n); for (i = 0; i < n; i++) { f = scanf("%d", &wu[i]); } //初始化 for (i = 0; i < n; i++) { dp[i][0] = 0; } for (j = v; j >= wu[0]; j--) { dp[0][j] = dp[0][j - wu[0]] + wu[0]; } //递推 for (i = 1; i < n; i++)//对人遍历 { for (j = 0; j <= v; j++)//对每个j遍历 { if (j < wu[i])//物品i不选 { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Max(dp[i - 1][j], (dp[i - 1][j - wu[i]] + wu[i]));//递推 } }//打印dp } /*for (i = 0; i < n; i++) { for (j = 0; j <= v; j++) { printf("%d ", dp[i][j]); } printf("\n"); } */ printf("%d", v - dp[n-1][v]); }
0.0分
1 人评分
采药 (C++代码)浏览:1322 |
【计算两点间的距离】 (C语言代码)浏览:1159 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:806 |
C语言训练-角谷猜想 (C++代码)(3N+1问题)浏览:1837 |
妹子杀手的故事 (C语言代码)浏览:1276 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1199 |
Cylinder (C语言描述+详细分析)浏览:3333 |
局部变量作函数返回值的问题浏览:1020 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:515 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2230 |