分佈估計演算法求解0 1揹包問題演算法的C語言程式

1樓：go浪人生

思路是：

1、先將所有東西按價值和重量的比值（價重比）從大到小排列。這裡我用的氣泡排序。

2、將價重比大的先放到揹包裡。直到揹包不能再放為止。此時**就是最大的。

你應該能看懂。

#include

#include

#include

#define limit 100

#define tn 20

typedef structthings;

void swap_things(things *t1, things *t2) // 只是一個交換函式而已。

void sort_things(things t, int n) // 排序函式，按照價重比排序（**與重量的比值）}}

void select_things(things t, int n, int limit) // 這個函式用來選擇要放進去的東西

列印放進去的東西的總重量和總**

}int main(void)

sort_things(t,tn);

select_things(t,tn,limit);

printf("weight\tvalue\tselected\n");

for(i=0;i

printf("%d\t%d\t%d\n",t[i].weight,t[i].value,t[i].selected);

return 0;}

2樓：匿名使用者

#include

#include

using namespace std;

int mval,nval;

int sum;

int *pout;

void calfun(int m,int n)

c語言，演算法，動態規劃。對於0-1揹包問題，我有個小疑問。

3樓：匿名使用者

dp(i,j)表示前i件物品選擇任意件後放進最大容量為j的揹包的最大價值。

顯然，dp(0,j)=0，dp(i,0)=0。

對於第i件物品，有兩種情況：

一、不放進揹包，則最大價值為前i-1件物品可以放進容量為j的揹包的最大價值，即dp(i,j)=dp(i-1,j)

二、放進揹包，則最大價值為第i件物品價值加上前i-1件物品卡伊放進容量為j-w[i]的揹包的最大價值，即dp(i,j)=v[i]+dp(i-1,j-w[i)

綜合兩種情況 dp(i,j)=max

0-1揹包問題的多種解法**（動態規劃、貪心法、回溯法、分支限界法）

4樓：匿名使用者

一.動態規劃求解0-1揹包問題

/* 0-1揹包問題：

c語言動態規劃——0-1揹包問題

5樓：匿名使用者

以前寫的 自己看吧

#include

int w[5]=,p[5]=;

int c=7,n=4;

int cw=0,cp=0,bestp=0;

int x[10]=;

void try(int k)

else

}main()

6樓：匿名使用者

clrscr(); 這是什麼東西？

我在刪除它後編譯成功。。

也不知道結果對不

計算機演算法分析考試：動態規劃0-1揹包問題，怎麼算

7樓：匿名使用者

問題描述：

給定n種物品和一揹包，物品i的重量是wi，其價值為vi，揹包的容量為c。問應如何選擇裝入揹包的物品（物品不能分割），使得裝入揹包中物品的總價值最大?

抽象描述如下：

x[n]:表示物品的選擇，x[i]=1表示選擇放進物品i到揹包中。

問題分析：

1.抽象之後揹包問題轉換為找到一個最優的陣列，x1，x2，.....,xn的0-1序列。

2.假設最優解的序列為x1，x2，.....,xn，能使揹包容量c的總價值最大.

如果，x1=1，則x2,...,xn是c-w1容量的揹包的總價值依然是最大的序列；

如果，x1=0，則x2,....,xn是c容量的揹包的總價值依然是最大的序列。

這就是我們所說的最優子結構性質。

3.進一步分析：我們用m(i,j)表示為已經判斷好了1:i-1的序列的揹包最大價值，並且此時的揹包剩餘的容量為j，對物品i進行判斷

如果j>wi, 就只要做出選擇wi和不選擇wi情況下，哪種更能使揹包的總價值更大：m(i,j)=max(注意這是個遞迴式)

如果j= wn)；

m(n,j)=0   (0<=j< wn)

m(0,c)=0

最終的結果：m(1,c）

4.依次我們就得到了一個遞迴的表示式：

5.如果單純的從利用遞迴，重複計算了很多的值，耗費的時間是很大的，動態規劃還需避免這種重複計算，怎樣自頂向下或自底向上的計算呢？

採用列表的方法就可以很好的分析設計自頂向下或自底向上的計算的演算法了

舉例分析：

n=3,c=6,w= v=

m[i][j]=max

列表如下：

最左邊箭頭：我們計算的方向，從第3行開始向上計演算法值。

表中紅色箭頭是我們通過選擇做出的結果：列如 m[2][3]=max，我們最終選擇了m[3][3-w[2]]+v[2]。

整個問題的最優解儲存在m[1][6]中。

求excel函式公式已知演算法，計算工資用的高手來

在f3中輸入或複製貼上此公式 if e3 26,d3,int d3 31 e3 下拉填充 在h3中輸入或複製貼上此公式 if e3 j1,int d3 31 e3 27 0 下拉填充 前提是將數值後面的 天 都刪除 應發工資 f3中公式 if 1 substitute e3,天 26,3000,30...

用簡便演算法計算 2 3 4 5 6 7 8 9 10 11

兗礦興隆礦 2 3 4 5 6 7 8 9 10 11 12 13 101 102 103 1 1 2 3 4 4 4 5 6 7 7 7 8 9 10 10 10 11 12 13 100 100 101 102 103 1 4 7 10 13 16 97 100 101 34 2 1717 原式...

求正態分佈中 x 的精確計算公式

浩笑工坊 x 1 2 1 1 n x 2 2n 1 2n 1 n 其中n從0求和到正無窮因為正態分佈是超越函式，所以沒有原函式，只能用級數積分的方法。稱其分佈為高斯分佈或正態分佈，記為n 2 其中為分佈的引數，分別為高斯分佈的期望和方差。當有確定值時，p x 也就確定了，特別當 0，2 1時，x的分...