P1049 装箱问题——题解2020.10.14

P1049 装箱问题

思路分析

• 从 n 个物品中选出若干个装入箱子，使得箱子剩余空间最小，每个物品都有两种状态，装入或不装入，可以枚举出所有情况求出剩余最小空间；
• 定义一个较大的变量 ans 表示剩余最小空间，遍历每一种情况与之对比，求出最小的值即为本题结果；

注意事项

• 由题可知：0 ≤ V ≤ 20000，0 < n ≤ 30；所以存储物品体积的数组定义为 w[40]，ans 初始化为 20000；

代码实现

#include <stdio.h>
int V, n, ans = 20000;
int v[40];
int f(int, int);
int main() {
    int i;scanf("%d%d", &V, &n);for (i = 0; i < n; i++)scanf("%d", &v[i]);f(V, 0);printf("%d", ans);} 
int f(int V, int i) {
    if(i == n){
    if(V < ans)ans = V;return ans; }if(V - v[i] >= 0)f(V - v[i], i + 1);f(V, i + 1);
}