装箱问题

[编程题]装箱问题

热度指数：6685 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

1个整数，表示箱子剩余空间。

示例1

输入

输出

算法知识视频讲解

cs小白_

#include <stdio.h>
#include <string.h>
int max(int a,int b){
    return (a>b?a:b);
}
int main() {
    int v, n;
    scanf("%d %d", &v, &n);
    int w[n+1];
    w[0]=0;
    int dp[n+1][v+1];
    memset(dp, 0, sizeof(dp));
    for (int i=1; i<=n; i++) {
        scanf("%d",&w[i]);
    }
    for (int i=1; i<=n; i++) {
         for (int j=1; j<=v; j++) {
                if(j-w[i]<0){
                    dp[i][j]=dp[i-1][j];
                }
                else {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
                }
         }
    }
     
    printf("%d", v-dp[n][v]);
    
    return 0;
}

发表于 2024-11-30 12:06:24 回复(0)