题意
给定一个载重量为 M 的背包, 考虑 n 个物品, 其中第 i 个物品的重量 wi , 价值 vi (1≤i≤n), 要求把物品装满背包, 且使背包内的物品价值最大.
有两类背包问题 (根据物品是否可以分割), 如果物品不可以分割, 称为 0-1 背包问题 (动态规划); 如果物品可以分割, 则称为背包问题 (贪心算法).
代码
- #include <iostream>
- 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;
- }
来源: http://www.bubuko.com/infodetail-3257278.html