解题思路:
注意事项:
参考代码:
/*装箱问题。有一个箱子容量为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语言训练-字符串正反连接 (C语言代码)浏览:692 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:716 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:569 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:1031 |
兰顿蚂蚁 (C++代码)浏览:1091 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:574 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:640 |
【计算球体积】 (C语言代码)浏览:1102 |
最小公倍数 (C语言代码)浏览:1029 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)from DQM浏览:666 |