【題目描述】

有一個箱子容量為V（正整數，0≤v≤20000），同時有n個物品（0< n ≤30），每個物品有一個體積（正整數）。

要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。

【輸入】

第一行是一個整數V，表示箱子容量。

第二行是一個整數n，表示物品數。

接下來n行，每行一個正整數（不超過10000），分別表示這n個物品的各自體積。

【輸出】

一個整數，表示箱子剩余空間。

【輸入樣例】

24
6
8
3
12
7
9
7

【輸出樣例】

0

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 50 #define MOD 2520 #define E 1e-12 using namespace std; int n,V; int w[50],f[20000]; void ZeroOnePack(int weight) {for(int v=V;v>=weight;v--)f[v]=max(f[v],f[v-weight]+weight); }int main() {cin>>V>>n;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1;i<=n;i++)ZeroOnePack(w[i]);cout<<V-f[V]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的装箱问题（信息学奥赛一本通-T1295）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。