You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
35 lines
792 B
35 lines
792 B
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
#define NUM 50
|
|
|
|
//这里假设 w[], v[] 已按要求排好序
|
|
void Knapsack(int n,float M,float v[],float w[],float x[]) {
|
|
int i;
|
|
for(i = 1; i <= n; i++) x[i] = 0; //初始化数组
|
|
float c = M;
|
|
for(i = 1; i <= n; i++) { //全部被装下的物品,且将 x[i] = 1
|
|
if(w[i]>c) break;
|
|
x[i] = 1;
|
|
c -= w[i];
|
|
}
|
|
if(i <= n) x[i] = c / w[i]; //将物品i 的部分装下
|
|
}
|
|
|
|
int main() {
|
|
float M = 50; //背包所能容纳的重量
|
|
float w[] = {0,10,20,30}; //这里给定的物品按价值降序排序
|
|
float v[] = {0,60,100,120};
|
|
float x[NUM]; //存储每个物品装入背包的比例
|
|
|
|
int n = (sizeof(w) / sizeof(w[0])) - 1;
|
|
|
|
Knapsack(n, M, v, w, x);
|
|
|
|
for(int i = 1; i <= n; i++)
|
|
cout << "物品 " << i << " 装入的比例: " << x[i] << endl;
|
|
return 0;
|
|
}
|
|
|
|
|