C++解决背包问题（Knapsacks Problem）

概述C++解决背包问题（Knapsacks Problem）

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

总的来说，背包问题是一种动态优化问题。
背包载重量一定，给定一组物品，没件物品有自己的价值和重量，问题要求在不超过背包载重前题下，怎样让载入的物品价值和最大？假如有物品如下：
       物品号           物品名               重量             价钱
          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）的重量了，以此类推，只考虑他的每个载重量的最优解，以每个物品为单位以此加入，得到最优解数列。

#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;}

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C++解决背包问题（Knapsacks Problem）全部内容，希望文章能够帮你解决C++解决背包问题（Knapsacks Problem）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。