解题思路:
注意事项:
参考代码:
/*装箱问题。有一个箱子容量为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语言代码)浏览:1335 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:563 |
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:584 |
简单的a+b (C语言代码)浏览:724 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C++代码)(手动优化一下计算)浏览:1286 |
川哥的吩咐 (C++代码)浏览:1019 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:790 |
C语言训练-数字母 (C语言代码)浏览:609 |
1642题解浏览:717 |
1017题解浏览:606 |