- #include <stdio.h>
- /* Geedy-knapsack Algorithm
- procedure GREEDY-KNAPSACK(P,W,M,X,n)
- //P(1:n)和W(1:n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n
- 件物品的效益值和重量。M是背包的容量大小,而X(1:n)是解向量//
- real P(1:n), W(1:n), X(1:n), M, cu;
- integer i,n
- X←0 //将解向量初始化为0//
- cu←M //cu是背包的剩余容量//
- for i←1 to n do
- if W(i) > cu then exit endif
- X(i) ←1
- cu ←cu-W(i)
- repeat
- if i≤n then X(i) ←cu/W(i) endif
- end GREEDY-KNAPSACK
- */
- int main ()
- {
- /* n 为物品种类数目
- M 为限制总重量
- cu 为剩余限制重量
- A 为包内物品总值
- P[] 为第 i 件物品价值
- W[] 为第 i 件物品单件重量
- X[] 为解向量
- 物品要按P[i]/W[i] > P[i+1]/W[i+1] 顺序排列 */
- int n = 4, M = 54, P[4] = {16, 20, 18, 10}, W[4] = {12, 16, 24, 15};
- double X[4], cu, A = 0.0;
- int i, j, k;
- for(i = 0; i < n; i++)
- X[i] = 0;
- cu = M;
- for(i = 1; i <= n; i++) {
- if(W[i-1] > cu)
- continue;
- X[i-1] = 1;
- cu = cu - W[i-1];
- }
- for(i = 1; i <= n; i++) {
- if(!X[i-1]) {
- X[i-1] = (double) cu / W[i-1];
- break;
- }
- }
- printf("ans: \\n");
- for(j = 0; j < n; j++) {
- printf("X[%d]: %.3f\\n", j, X[j]);
- A = A + P[j]*X[j];
- }
- printf("\\ntotal value: %f \\n", A);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/240720134779.html
来源: http://www.codesnippet.cn/detail/240720134779.html