返回顶部

收藏

C++解决背包问题(Knapsacks Problem)

更多

总的来说,背包问题是一种动态优化问题。 背包载重量一定,给定一组物品,没件物品有自己的价值和重量,问题要求在不超过背包载重前题下,怎样让载入的物品价值和最大?假如有物品如下: 物品号 物品名 重量 价钱 0 李子 4 4500 1 苹果 5 5700 2 橘子 2 2250 3 草莓 1 1100 4 甜瓜 6 6700

  解决问题要用到动态规划(Dynamic programming),从空集合开始,每增加一个元素就先求出该阶段的最优解,知道所有的元素加入到集合中,最后就可以得到最优解。其实是求出了在每个重量单位的最优解,是一个最优解数列。
  代码中value代表目前最优解所得的总和,item表示最后一个放入背包的水果。
 我们可以这样想,把问题逆过来考虑,假设最后放入的是2#,则之前背包只能放下(8-2)的重量了,后二个放入的是苹果,则之前只能放入(8-2-5)的重量了,以此类推,只考虑他的每个载重量的最优解,以每个物品为单位以此加入,得到最优解数列。```cpp

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++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论