1樓:匿名使用者
這裡不但有這一題的詳細解答,還有其他相似題目,可供參考。
附程式:
program ll;
vars,i,j,n,min,v:longint;
a:array[0..10000] of longint;
procedure run(k,va:longint);
begin
if va<=min then min:=va;
if k<=n then
begin
if va>=a[k] then run(k+1,va-a[k]);
run(k+1,va); /////////////和其他幾個dfs一樣有兩種情況,但中間不能用else連線!!
end; /////////////乙個else搞垮了我!!!!!!
end;
begin
readln(v);
readln(n);
s:=0;
for i:=1 to n do
begin
readln(a[i]);
s:=s+a[i];
end;
min:=v;
if s<=n then min:=v-s
else run(1,v);
writeln(min);
end.
/////////////////////當然這道題還可以進一步剪枝優化。 如在run中,加入當前所剩的所有箱子如果不能裝滿(即後面的箱子),則可直接把後面的箱子全部區到!!!!!!
varf0,f1:array[0..20000] of boolean;
box:array[0..30] of integer;
v,n,i,j:integer;
begin
readln(v);readln(n);
for i:=1 to n do
readln(box[i]);
fillchar(f0,sizeof(f0),0);
f0[0]:=true;
for i:=1 to n do
begin
f1:=f0;
for j:=box[i] to v do
if f0[j-box[i]] then f1[j]:=true;
f0:=f1;
end;
for i:=v downto 0 do
begin
if f1[i] then begin
writeln(v-i);halt
end;
end;
writeln(v);
end.
強悍的dp,至今還不明白!!!!!
var a:array[0..20000] of longint;
i,j,n,v,t:longint;
begin
readln(v);readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
readln(t);
for j:=v-t downto 0 do
if a[j]+t>a[j+t] then a[j+t]:=a[j]+t;
end;
writeln(v-a[v]);
end.
//////////////////////王冀的強悍動態!!!////////
其實就是乙個簡單的揹包
2樓:匿名使用者
vari,j,n,v:longint;
f:array[0..31,0..20001] of boolean;
t:array[0..100] of longint;
begin
readln(v);readln(n);
for i:=1 to n do read(t[i]);
f[0,0]:=true;
for j:=1 to n do f[0,j]:=false;
for i:=1 to n do
for j:=0 to v do
if (j>=t[i]) and (f[i-1,j-t[i]]) or (f[i-1,j]) then f[i,j]:=true
else f[i,j]:=false;
for i:=v downto 0 do
begin
if f[n,i] then break;
end;
writeln(v-i);
end.
pascal 裝箱問題(要有注釋,越詳細越好)
3樓:匿名使用者
var m,n,i,w,x:longint;
f:array[0..20001] of longint;
begin
read(m,n);
for i:=1 to n do
begin
read(w);
for x:=m downto w do
if f[x-w]+w>f[x] then f[x]:=f[x-w]+w;
end;
write(m-f[m]);
end.
4樓:匿名使用者
var v,n,max,i,j:longint;a:array[1..30]of longint;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r) div 2];
repeat
while a[i]x do dec(j);
if i<=j then begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if lmax)and(a[i]<>0) then begin max:=a[i];a[i]:=0;end;
v:=v-max;
max:=0;
end;
writeln(v);
end.
5樓:匿名使用者
dp!!!——動態規劃!!!
裝箱問題 怎麼編 pascal 上林杯2010年最後一題 pack.pas
6樓:匿名使用者
var f: array [0..20000] of boolean;
c: array [1..30] of longint;
i,j,n,v: longint;
begin
readln(v);
readln(n);
fillchar(f,sizeof(f),false);
for i:=1 to n do readln(c[i]);
f[0]:=true;
for i:=1 to n do
for j:=v downto c[i] do f[j]:=f[j-c[i]] or f[j];
for i:=v downto 0 do
if f[i] then begin writeln(v-i); break; end;
end.
7樓:弱弱的
f[i] =true 表示已裝體積為i這種狀態可以到達,若為flase則表示不可到達
用a陣列儲存物品體積,n為物體種類,v為箱子容量
核心**如下:
for i:=0 to v do f[i]:=false;
f[0]:=true; //一開始已裝體積為0,除0外的體積都不可以到達
for i:=1 to n do //列舉每乙個物品
for j:=v-a[i] downto 0 do //列舉體積 注意要倒著列舉,若正著列舉物品會被多次使用
if f[j] then f[j+a[i]]:=true; //如果j的體積已經可以到達那麼加上當前物品體積的狀態也可以到達
最後只需要倒著找乙個最接近v的值輸出即可:
for i:=v downto 0 do
if f[i] then
begin
writeln(v-i);
break;
end;
pascal新裝箱問題
8樓:匿名使用者
vara:array[1..6] of longint;
i,ans:longint;
function sum:longint;
vari:longint;
begin
sum:=0;
for i:=1 to 6 do inc(sum,a[i]);
end;
begin
while true do
begin
for i:=1 to 6 do read(a[i]);readln;
if sum=0 then break;
ans:=a[6];a[6]:=0;
a[1]:=a[1]-a[5]*11;if a[1]<0 then a[1]:=0;
ans:=ans+a[5];a[5]:=0;
ans:=ans+a[4];
if a[2]>=a[4]*5 then
begin
a[2]:=a[2]-a[4]*5;
a[4]:=0;
endelse
begin
a[1]:=a[1]-(20*a[4]-4*a[2]);
if a[1]<0 then a[1]:=0;
a[2]:=0;
a[4]:=0;
end;
ans:=ans+a[3] shr 2;
a[3]:=a[3] mod 4;
if a[3]>0 then
begin
inc(ans);
if a[2]<=7-a[3]*2 thenbegin
a[1]:=a[1]-(36-9*a[3]-4*a[2]);
if a[1]<0 then a[1]:=0;
a[2]:=0;
end;
if a[2]>7-a[3]*2 thenbegin
a[2]:=a[2]-7+a[3]*2;
a[1]:=a[1]-(36-9*a[3]-4*(7-a[3]*2));
if a[1]<0 then a[1]:=0;
end;
a[3]:=0;
end;
ans:=ans+a[2] div 9;
a[2]:=a[2] mod 9;
if a[2]>0 then
begin
inc(ans);
a[1]:=a[1]-(36-a[2]*4);
end;
if a[1]<0 then a[1]:=0;
ans:=ans+a[1] div 36;
a[1]:=a[1] mod 36;
if a[1]>0 then inc(ans);
writeln(ans);
end;
end.
9樓:
type
aaa=array[1..6] of longint;
varf:array[1..31,1..6] of longint=((0,0,0,0,0,1),
(11,0,0,0,1,0),
(0,5,0,1,0,0),
(4,4,0,1,0,0),
(8,3,0,1,0,0),
(12,2,0,1,0,0),
(16,1,0,1,0,0),
(20,0,0,1,0,0),
(0,0,4,0,0,0),
(5,1,3,0,0,0),
(9,0,3,0,0,0),
(6,3,2,0,0,0),
(10,2,2,0,0,0),
(14,1,2,0,0,0),
(18,0,2,0,0,0),
(7,5,1,0,0,0),
(11,4,1,0,0,0),
(15,3,1,0,0,0),
(19,2,1,0,0,0),
(23,1,1,0,0,0),
(27,0,1,0,0,0),
(0,9,0,0,0,0),
(4,8,0,0,0,0),
(8,7,0,0,0,0),
(12,6,0,0,0,0),
(16,5,0,0,0,0),
(20,4,0,0,0,0),
(24,3,0,0,0,0),
(28,2,0,0,0,0),
(32,1,0,0,0,0),
(36,0,0,0,0,0));
a:aaa;
i,j,m,k:longint;
ans:array[0..20,0..20,0..20,0..20,0..20,0..20] of longint;
function check(a:aaa):boolean;
var i:longint;
begin
check:=true;
for i:=1 to 6 do if a[i]>0 then exit(false);
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function find(a:aaa):longint;
var i,j:longint;
b:aaa;
t:boolean;
begin
if check(a) then exit(0);
find:=maxlongint;
for i:=1 to 31 do
begin
t:=false;
for j:=1 to 6 do
if (f[i,j]>0) and (a[j]>0) thenbegin
t:=true;
break;
end;
if t then
begin
for j:=1 to 6 do
b[j]:=a[j]-f[i,j];
find:=min(find(b)+1,find);
end;
end;
end;
begin
while true do
begin
for i:=1 to 6 do read(a[i]);
readln;
if a[1]+a[2]+a[3]+a[4]+a[5]+a[6]=0 then break;
writeln(find(a));
end;
end.
一道pascal問題求解,一道Pascal問題求解
用hash壓縮下,時空效率就很高了。先放在陣列,再用for迴圈,迴圈是 a to z 然後再用選擇排序 for i 1 to n 1 do for j i 1 to n do begin t a i a i a j a j t end 一道pascal問題求解 按題意,分子中能分解出sum1個2,分...
pascal求解問題描述由檔案給出n個1到30000間無
我覺得這個資料範圍完全不用什麼快排,大材小用,30000內的數直接計數排序就可以了 你的程式就是計數排序 你這麼做我覺得是完全正確的,我也寫了個資料生成器來試了試,你的程式時間複雜度完全過關,正確性應該沒有問題.空間不應該有問題,你的空間複雜度十分低,低到了基本可以忽略的地步,不可能mle的 學過快...
情景題求解答,情景面試問題應該怎麼回答?求解答
沒補充了嗎?失事地點?大概的時間?而且為什麼飛機上會有高爾夫球杆。攜帶有限制麼,很多細節不清楚呢。心裡有點想法的 現在比較急。明天給你答案。如果沒有補充我也能回答的。線分析一下。純屬個人見解 大刀 防身用,在野外身邊有吧 底氣會比較足。如果小一點會更加好。畢竟攜帶不方便。火柴 小巧便攜,肯定帶,雖然...
大神求解,C語言問題,C語言的乙個題,大神求解!
include void scanf file 迴圈j次 後 並獲得合併的資料 存放到total num 寫資料 fclose fo 關閉檔案 fclose fi 至於你說的字串函式格式都是大同小異 無非就是 s d c 最長用的就是sprintf char path sprintf path,s ...
c語言就1題大家都會,C語言問題,第1題,求解答。。。
pic 函式實現的功能是 輸出len個c變數對應的字元。例如初次呼叫時 pic i 2 j 2,語句完成的的功能是,輸出10個 字元 第乙個實參i 2 j 2結果為10,第二個實參為 分別值傳遞給了第乙個型參 len和第二個型參c 相當於len 10 c 所以迴圈10次,輸出10個 以此類推。c語言...