题目

题目描述

有一个箱子容量为 V （正整数， $0 <= V <=20000$ ），同时有 n 个物品（ $0<n<=30$ ，每个物品有一个体积（正整数）。

要求 nn 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
注：此问题区分大小写

输入格式

1 个整数，表示箱子容量

1 个整数，表示有 n 个物品

接下来 n 行，分别表示这 n 个物品的各自体积

输出格式

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

样例输入

样例输出

0

来源

NOIp2001普及组第4题

题解

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,v;
int w[31];
int f[20001];

int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=v;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+w[i]);
        }
    }
    printf("%d",v-f[v]);
    return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int n,v;

int w[31];

int f[20001];

int main(){

scanf("%d%d",&v,&n);

for(int i=1;i<=n;i++){

scanf("%d",&w[i]);

}

for(int i=1;i<=n;i++){

for(int j=v;j>=w[i];j--){

f[j]=max(f[j],f[j-w[i]]+w[i]);

}

printf("%d",v-f[v]);

return 0;

}

发送评论编辑评论

题目