假设有一个背包的负重最多可达8公斤,而希望在背包中装入负重范围内可得之总价物品,假设是水果好了,水果的编号、单价与重量如下所示:
0 |
李子 |
4KG |
NT$4500 |
1 |
苹果 |
5KG |
NT$5700 |
2 |
橘子 |
2KG |
NT$2250 |
3 |
草莓 |
1KG |
NT$1100 |
4 |
甜瓜 |
6KG |
NT$6700 |
解法
背包问题是关于最佳化的问题,要解最佳化问题可以使用“动态规划”(Dynamic programming),从空集合开始,每增加一个元素就先求出该阶段的最佳解,直到所有的元素加入至集合中,最后得到的就是最佳解。
以背包问题为例,我们使用两个阵列value与item,value表示目前的最佳解所得之总价,item表示最后一个放至背包的水果,假设有负重量 1~8的背包8个,并对每个背包求其最佳解。
逐步将水果放入背包中,并求该阶段的最佳解:
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
0 |
0 |
4500 |
4500 |
4500 |
4500 |
9000 |
item |
- |
- |
- |
0 |
0 |
0 |
0 |
0 |
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
0 |
0 |
4500 |
5700 |
5700 |
5700 |
9000 |
item |
- |
- |
- |
0 |
1 |
1 |
1 |
0 |
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
0 |
2250 |
2250 |
4500 |
5700 |
6750 |
7950 |
9000 |
item |
- |
2 |
2 |
0 |
1 |
2 |
2 |
0 |
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
由最后一个表格,可以得知在背包负重8公斤时,最多可以装入9050元的水果,而最后一个装入的水果是3号,也就是草莓,装入了草莓,背包只能再放入7公斤(8-1)的水果,所以必须看背包负重7公斤时的最佳解,最后一个放入的是2号,也就是橘子,现在背包剩下负重量5公斤(7-2),所以看负重5公斤的最佳解,最后放入的是1号,也就是苹果,此时背包负重量剩下0公斤(5-5),无法再放入水果,所以求出最佳解为放入草莓、橘子与苹果,而总价为9050元。
C语言实现
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 8 // 重量限制
#define N 5 // 物品种类
#define MIN 1 // 最小重量
struct body {
char name[20];
int size;
int price;
};
typedef struct body object;
int main(void) {
int item[LIMIT+1] = {0};
int value[LIMIT+1] = {0};
int newvalue, i, s, p;
object a[] = {{"李子", 4, 4500},
{"苹果", 5, 5700},
{"橘子", 2, 2250},
{"草莓", 1, 1100},
{"甜瓜", 6, 6700}};
for(i = 0; i < N; i++) {
for(s = a[i].size; s <= LIMIT; s++) {
p = s - a[i].size;
newvalue = value[p] + a[i].price;
if(newvalue > value[s]) {// 找到阶段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
printf("物品\t价格\n");
for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) {
printf("%s\t%d\n",
a[item[i]].name, a[item[i]].price);
}
printf("合计\t%d\n", value[LIMIT]);
return 0;
}
分享到:
相关推荐
数据结构中背包问题c语言实现
贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现...
背包问题C语言实现, 如要不同格式的输出,修改main函数即可
01背包问题是一个很经典的问题,在这里我用回溯法解决。希望大家一起来探讨呀!
经典的背包问题------------- c语言实现 TU2。0上使用的
贪心算法 背包问题 c语言 绝对无误 运行成功
0-1背包问题的实现代码,可直接编译执行,算法经过了两步的优化
为C语言课程设计写的基于贪心法的背包问题,包含全部4种贪心策略
完全版分支界限法求解背包问题,易于理解 分支界限法0-1背包问题
背包问题算法代码C语言实现
背包问题,C语言实现,背包问题,C语言实现,背包问题,C语言实现,背包问题,C语言实现背包问题,C语言实现,背包问题,C语言实现
基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现...
基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心...
用贪心法解决背包问题的源代码,在vc++环境下也可以运行
运用贪心算法解决背包问题,也可以理解为装箱问题。本文设置箱体最大体积是264,
用c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15
01背包问题真正的c语言回溯法实现,我在自己试验过的
背包问题哦,采用c语言中链表的知识点,已经挺完备了,欢迎交流
背包问题 求从n个体积分别为w1,w2...wn的物品中挑选若干件恰好装满体积为T的背包,求所有解
背包问题的递归算法,很好 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。