PASCAL 01揹包，PASCAL 01揹包

1樓：匿名使用者

varf:array [1..35000] of longint;

b,c:longint;

v:array [1..21] of longint;

i,j:longint;

begin

read(c,b);

for i:=1 to b do read(v[i]);

for i:=1 to b do for j:=c downto v[i] do

if f[j]

writeln(f[c]);

end.

2樓：匿名使用者

vara:array[0..35000]of boolean;

f:array[1..21]of longint;

b,c,i,j:longint;

begin

fillchar(a,sizeof(a),false);

a[0]:=true;

read(c,b);

for i:=1 to b do

read(f[i]);

for i:=1 to b do

for j:=c downto f[i] doa[j]:=a[j-f[i]] or a[j];

for i:=c downto 0 do

if a[i] then begin

writeln(i); halt;

end;

end.

pascal 01揹包問題

3樓：冠睿才

program baozi1;

var a:array[0..100000]of longint;

v,p,w,c:array[0..100]of longint;

n,m,i,j:longint;

begin

readln(m,n);

for i:=1 to m do

read(v[i],w[i]);

for i:=1 to m do

for j:=n downto v[i] doif a[j]

writeln(a[n]);

readln;

readln;

end.

4樓：

這題我還是覺得用動態規劃比較好，

當然也可以直接根據狀態轉移方稱寫個遞迴（不懂自己去看動態規劃）如果用money表示剩下的錢，i表示前i個物品則f（i,money）=max

你說用搜尋寫，那就

function f(x,y:longint);

begin

這裡是邊界條件

f<-max

end;

pascal 01揹包怎麼知道選了哪幾項？

5樓：

揹包方程f[i,j]:=max

我們設g[i,j]為記錄型別，表示轉移到f[i,j]的上一步的j的值，即：

若f[i,j]=f[i-1,j] 則g[i,j]:=j;

若f[i,j]=f[i-1,j-w[i]] 則g[i,j]:=j-w[i];

這個過程在動態規劃主過程裡實現。

之後用dfs

search(n,m);

深搜每一層時判斷g[x,y]是等於y還是等於y-w[x]，若前者則此物品選了，後者則此物品沒有選。然後後序輸出即可。

附深搜(現編，意會~具體細節你自己去弄弄吧)

procedure search(x,y:longint);

begin

if x=0 then exit;

if g[x,y]=y-w[i] then begin search(x-1,y-w[i]);write(x,' ');end else search(x-1,y);

end;

6樓：

指標，或者b陣列裡辨析

7樓：匿名使用者

我用boolean陣列超空間似的儲存狀態b[i,j,k]表示f[i,j]時第k個物體選不選，

超猥瑣的雜湊，在vijos上ac，不過超記憶體了（vijos的評測機強）

pascal 01揹包問題

8樓：懊木貿誓鮮

具體就是二維陣列用滾動陣列來優化啊、、

可以直接將方程改為

for i:=1 to n do

for j:=v downto vv[i] doif v-vv[i]>0 then

f[v]:=max(f[v],f[v-vv[i]]);

f[v] 就相當於之前的f[i,v]、、

具體，你說的表示方案是神馬意思？、

pascal 01揹包

9樓：

這是動態規劃

program knapsack02;

const maxm=200;maxn=30;

type ar=array[1..maxn] of integer;

var m,n,j,i:integer;

c,w:ar;

f:array[0..maxn,0..maxm] of integer;

function max(x,y:integer):integer;

begin

if x>y then max:=x else max:=y;

end;

begin

readln(m,n);

for i:= 1 to n do

readln(w[i],c[i]);

for i:=1 to m do f(0,i):=0;

for i:=1 to n do f(i,0):=0;

for i:=1 to n do

for j:=1 to m do

begin

if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])｛如果當前揹包可以裝入揹包i且裝入後最大則裝入i｝

else f[i,j]:=f[i-1,j];

end;

writeln(f[n,m]);

10樓：

你是否知道動態規劃,如果不懂,這道題暫時先別看,先了解動態規劃

如果知道,解釋如下

f[i,j]表示取前i件物品,在重量不超過j的情況下所能獲得的最大價值

program knapsack02;

const maxm=200;maxn=30;

type ar=array[1..maxn] of integer;

var m,n,j,i:integer;

c,w:ar;

f:array[0..maxn,0..maxm] of integer;

function max(x,y:integer):integer; //取兩者中較大這的函式

begin

if x>y then max:=x else max:=y;

end;

begin

readln(m,n);

for i:= 1 to n do

readln(w[i],c[i]);

for i:=1 to m do f(0,i):=0; //邊界

for i:=1 to n do f(i,0):=0; //邊界

for i:=1 to n do

for j:=1 to m do

begin

if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])

else f[i,j]:=f[i-1,j]; //狀態轉移方程

end;

writeln(f[n,m]);

該狀態轉移方程含義

因為迴圈到第i件物品時,可以取(f[i-1,j-w[i]]+c[i]),也可不取(f[i-1,j]) ,去兩者中較大的,以區域性最優推出全域性最優

11樓：匿名使用者

也可以用遞迴的

明天就要去noi 複賽普及組 考試了

誰再指點指點~~

pascal的01揹包程式

12樓：手機使用者

揹包是什麼知道撒

01揹包是指每個物品只能用一次

完全揹包指的是每個物品都能無限使用

沒什麼技巧，dp類的明確了狀態後就寫起來快了，寫多了程式自然也就有經驗了，有經驗就能快速的推出狀態，總之就是多寫題

程式的不同很簡單

完全揹包

for i:=1 to n do //列舉1-n的物品

for j:=a[i] to m do //列舉1-m的能背出來的範圍

f[j]:=f[j] or f[j-a[i]];

01揹包

for i:=1 to n do //列舉1-n的物品

for j:=m downto a[i] do //列舉1-m的能背出來的範圍

f[j]:=f[j] or f[j-a[i]];

注意，之前要先f[0]:=true；

可以看出，區別只在第二個迴圈的正倒，f是一個布林陣列，f[i]表示i這個數字能夠被組合出來

為什麼迴圈的正倒會導致這樣的區別呢？

我們舉個例子：

假設我們現在組合出了3，現在討論的物品體積是1，那麼,即a[i]=1, f[3]:=true;

當正迴圈時

當列舉到4的時候，f[4]=f[4] or f[4-1]=true，因為f[3]=true;

當列舉到5的時候，f[5]=f[5] or f[5-1]=true，因為f[4]=true;

顯然，這個「1」會被無限的使用下去直到到達m的上限

逆迴圈則相反

----------------

純原創，求最佳···請參考

13樓：

一維陣列的話建議你用boolean型來做，這樣的話可以節省很多空間。

14樓：匿名使用者

這個 那個 我是個大新手，看不懂額

pascal 01揹包問題（回溯） 5

15樓：大小魔法秀秀秀

#include

using namespace std;

int main()

;int s=14;

int k=8;

pascal(s,k,w);

system("pause");

return 0;

}int pascal(int s,int k,int w)else return pascal(s,k-1,w);

} 這個回溯是從後往前找的。6,7,1，這樣。用的是c++

16樓：

回溯的時間複雜度太高了，建議用dp

pascal 01揹包的程式，哪錯了？

17樓：匿名使用者

你所謂出錯的語句是用來清零的，因為一個程式在執行前所有的變數都是0或空，你可以試試先把這條語句去掉，看看是否還出錯 ，

當然，你f陣列根本沒有定義[0,i]與[i,0],先把這個改好再說吧

我個人認為，你除了這個小瑕疵以外，其餘的應該是對的，至少我執行起來沒有發現你所說的陣列c被清空的現象

pascal教程，怎麼使用pascal

第一節 pascal語言的特點。資訊學奧林匹克競賽是一項益智性的競賽活動，核心是考查參賽選手的智力和使用計算機程式設計解題的能力。資訊學奧林匹克競賽要求參賽選手有如下能力 針對競賽題目中的要求構建數學模型，構造出有效的演算法和選用相應的資料結構，寫出高階語言程式，上機除錯通過。程式設計是資訊學奧林匹...

pascal題。幫忙，pascal題。幫忙！！！

我這樣做 整數列嘛 首先就先輸入一個n來表示這個整數列有多少個整數varn integer a array 1.1000 of integer i,j,k integer begin readln n for i 1 to n do read a i j 1 k 0 repeat if a j a ...

pascal常見問題，關於Pascal語言問題 完整的

第一題是百錢百雞問題拓展，屬於列舉問題 program p1 vara,b,c integer begin for a 1 to 35 do for b 1 to 50 do begin c 90 a b if a 15 b 10 c 5 500 thenwriteln a,b,c end end....