1樓：匿名使用者
#include
#define n 100
int str[n];
int w[n];
int k=0;
void
backtrack(int i,int n,int m)if(i<=n&&m>0)
}}int
main()
printf("揹包中存放的物品的幾種情況分別為為:\n");//注意輸出結果有的相同，但他們的數目不同
backtrack(1,n,m);
printf("總方案數為:%d\n",k);
return 0;}
2樓：匿名使用者
對於你的bai揹包問題，只需du根據物品的種類用相zhi應數目的daofor迴圈就可以了，再版用乙個判權定語句，程式如下：
#include
#define max 20 //揹包容量
int main()
; //a[0]表示第一種物品體積，依次一樣printf("物品1 物品2 物品3 物品4\n");
for(i=0; a[0]*i<=max;i++)for(j=0; a[1]*j<=max;j++)for(k=0; a[2]*k<=max;k++)for(l=0; a[3]*l<=max;l++)if(max==(i*a[0]+j*a[1]+k*a[2]+l*a[3]))
printf("%d\t%d\t%d\t%d\n",i,j,k,l);
return 0;}
3樓：匿名使用者
深度優先搜尋 + 回溯。
或剪枝就行了。
4樓：匿名使用者
這問題沒大多意義啊。一般是考慮那種方案最優吧。方案數真的不好處理，一般是採用迴圈確定方案總數。
計算機上的揹包問題是什麼,怎麼解決,能不能說一下思路,最好有c或者
5樓：匿名使用者
下面是引用的一段說明，有揹包問題的描述以及各種演算法的**，當然有些是vb的，有些是c＋＋的，我覺得聽全面的，希望對你有所幫助。
1)登山演算法
用登山演算法求解揹包問題 function =dengshan(n,g,p,w) %n是揹包的個數，g是揹包的總容量，p是價值向量，w是物體的重量向量 %n=3;g=20;p=[25,24,15];w2=[18,15,10];%輸入量 w2=w; [y,i]=sort(-p./w2);w1=;x=;x1=; for i=1:length(i) w1(i)=w2(i(i)); end w=w1; for i=1:
n x(i)=0; res=g;%揹包的剩餘容量 j=1; while w(j)<=res x(j)=1; res=res-w(j); j=j+1; end x(j)=res/w(j); end for i=1:length(i) x1(i(i))=x(i); end x=x1; disp('裝包的方法是');disp(x);disp(x.*w2);disp('總的價值是：
');disp(p*x');
時間複雜度是非指數的
2)遞迴法
先看完全揹包問題
乙個旅行者有乙個最多能用m公斤的揹包，現在有n種物品，每件的重量分別是w1，w2，...,wn,
每件的價值分別為c1,c2,...,cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max 當x>=w[i] 1<=i<=n
可使用遞迴法解決問題程式如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,程式設計很簡單,但當m較大時,容易超時.
4.2 改進的遞迴法
改進的的遞迴法的思想還是以空間換時間,這只要將遞迴函式計算過程中的各個子函式的值儲存起來,開闢乙個
一維陣列即可
程式如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的揹包問題：給定乙個超遞增序列和乙個揹包的容量，然後在超遞增序列中選（只能選一次）或不選每乙個數值，使得選中的數值的和正好等於揹包的容量。
**思路：從最大的元素開始遍歷超遞增序列中的每個元素，若揹包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下乙個元素；若揹包剩餘空間小於當前元素值，則判斷下乙個元素
簡單模擬如下：
#define k 10
#define n 10
＃i nclude
＃i nclude
void create(long array,int n,int k)
else/*揹包剩餘空間小於當前元素值*/
cankao[i]=0;
} }void main()
; int i;
long value,value1=0;
clrscr();
create(array,n,k);
output(array,n);
printf("\ninput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,n);
for(i=0;i
＃i nclude
void create(long array,int n,int k)
else
cankao[i]=0;
} }int beibao1(long array,int cankao,long value,int n)
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
} void main()
; int cankao1[n]=;
int i;
long value,value1=0;
clrscr();
create(array,n,k);
output(array,n);
printf("\ninput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,n);
for(i=0;i=wi時： f(i,j)=max ①式
當0<=j fn( 1 ,c) 是初始時揹包問題的最優解。 以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。 因此最優解f ( 1 , 11 6 ) = m a x = m a x = m a x = 3 8。 現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。 依此類推，可得到所有的xi (i= 1.n) 值。 在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。 揹包問題c語言簡短**，大神們最好帶解釋和註釋，謝謝！！！ c語言，揹包問題，用遞迴演算法，下面這個怎麼程式設計，謝謝！ 6樓：匿名使用者 揹包問題是npc問題。直接用列舉演算法。要想增加效率，可以試著儲存重複狀態。 揹包問題(knapsack problem)是一種組合優化的np完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和**，在限定的總重量內，我們如何選擇，才能使得物品的總**最高。 問題的名稱**於如何選擇最合適的物品放置於給定揹包中。相似問題經常出現在商業、組合數學，計算複雜性理論、密碼學和應用數學等領域中。也可以將揹包問題描述為決定性問題，即在總重量不超過w的前提下，總價值是否能達到v？ 它是在2023年由merkel和hellman提出的。 演算法思路請參考百科 我想說的是 我這種方法迴圈最簡單 且語句正確 沒有多解現象 格式美觀 include void main include main 執行結果為 4種情況 公雞0只,母雞25只,小雞75只 公雞4只,母雞18只,小雞78只 公雞8只,母雞11只,小雞81只 公雞12只,母雞4只,小雞84只 百錢買百雞... 1，是取值運算子，因為你要判斷tt的值的情況，所以要用 2，tt 相當於 tt tt 1 這個是指標向後移動，不需要取值，謝謝，望採納 你的tt是指標吧。tt指向的是 位址 比如位址值為 10ff 1000 tt是取這個位址中儲存的資料，而tt 意思把tt指向的位址值 1，即tt現在指向了 10ff... include define offset 0.00001ffloat getpi float a pibefore piafter getpi a 1 return piafter int main 遞迴法 你好，公 bai式為dupi 1 1 2 1 4 1 6 1 8 1 n，c語言代 zhi...求c語言百雞問題的解，求C語言 百雞問題的解
c語言指標問題，求解答,C語言中的指標問題，求解答
C語言。求PI的近似值用c語言程式設計計算pi的近似值