A1133. 裝箱問題
1.0s 記憶體限制：
256.0MB
1096 AC次數：
404 平均分：
56.26
将本題分享到：
檢視未格式化的試題
送出
試題讨論
試題來源
NOIP2001 普及組
問題描述
有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30），每個物品有一個體積（正整數）。
要求n個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。
輸入格式
第一行為一個整數，表示箱子容量；
第二行為一個整數，表示有n個物品；
接下來n行，每行一個整數表示這n個物品的各自體積。
輸出格式
一個整數，表示箱子剩餘空間。
樣例輸入
24
6
8
3
12
7
9
7
樣例輸出
解析：01背包問題。
代碼：
#include<cstdio>
const int maxn=20000;
bool f[maxn+10];
void work()
{
int v,n,i,j,k;
scanf("%d%d",&v,&n);
for(f[0]=i=1;i<=n;i++)
{
scanf("%d",&k);
for(j=v-k;j>=0;j--)if(f[j])f[j+k]=1;
}
for(i=v;i>=0;i--)if(f[i])
{
printf("%d\n",v-i);
return 0;
}
}