題目描述
有一個箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30，每個物品有一個體積（正整數(shù)）。
要求n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。
輸入輸出格式
輸入格式： 一個整數(shù)，表示箱子容量
一個整數(shù)，表示有n個物品
接下來n行，分別表示這n 個物品的各自體積
輸出格式： 一個整數(shù)，表示箱子剩余空間。
輸入輸出樣例
輸入樣例#1： 24 6 8 3 12 7 9 7 輸出樣例#1： 0 說明
NOip2001普及組 第4題 DP： f[i,j]表示前i個物品在箱子重量為j時能放的最大體積。 j>=a[i] f[i,j]:=max(f[i-1,j],f[i-1,j-a[i]]+a[i]) j
var i,j,n,m:longint; f:array [0..31,0..20001] of longint; a:Array [0..31] of longint;begin readln(m); readln(n); for i:=1 to n do readln(a[i]); for i:=1 to n do begin for j:=1 to a[i]-1 do f[i,j]:=f[i-1,j]; for j:=a[i] to m do if f[i-1,j]>f[i-1,j-a[i]]+a[i] then f[i,j]:=f[i-1,j] else f[i,j]:=f[i-1,j-a[i]]+a[i]; end; writeln(m-f[n,m]);end.新聞熱點(diǎn)
疑難解答
