描述

有一個箱子容量為v(正整數，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積 (正整數)。要求從 n 個物品中，任取若千個裝入箱內，使箱子的剩余空間為最小。

格式

輸入格式

第一行，一個整數，表示箱子容量；
第二行，一個整數，表示有n個物品；
接下來n行，分別表示這n個物品的各自體積。

輸出格式

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

樣例1

樣例輸入1

24 6 8 3 12 7 9 7 Copy

樣例輸出1

0 Copy

限制

每個測試點1s

來源

noip2001普及組第四題

Solution:

#include<iostream> using namespace std; const int maxn=20010; int f[maxn]; int v[maxn];int main() {int m,n;cin>>m>>n;int i,j;for (i=1; i<=n; i++) {cin>>v[i];}for (i=1; i<=n; i++) {for (j=m; j>=v[i]; j--) {if (f[j]<f[j-v[i]]+v[i]) {f[j]=f[j-v[i]]+v[i];}}}cout<<m-f[m]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的装箱问题 vijos的全部內容，希望文章能夠幫你解決所遇到的問題。

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