解题思路:
注意事项:
参考代码:
/*装箱问题。有一个箱子容量为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语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:559 |
字符串对比 (C语言代码)浏览:1454 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:601 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:647 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:486 |
1157题解浏览:761 |
简单的a+b (C语言代码)浏览:569 |
矩形面积交 (C++代码)浏览:1199 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1452 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:981 |