背包问题

2019-11-11 05:03:08

字体：大中小

来源：转载

供稿：网友

题目：

假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示：

0 李子4KG $4500

1 苹果5KG $570

2 橘子2KG $225

3 草莓1KG $110

4 甜瓜6KG $670

思路

设有8个背包，负重从1,2…..8. 物品编号从0,1……4.两个循环嵌套在一起。从物品0开始，一次考虑负重1,2，到8. 然后物品1,2，到4.

每一个背包每一次考虑放入不放入这个物品。任意重量的任意物品考虑之后的背包都是最优解。

有两个‘指针’，记录当下考虑的背包，和减去当下这轮物品重量的背包。既，‘要不要退到某个最佳解腾出这个物品的重量，加上这个物品’

代码

#include <stdio.h>#include <stdlib.h>#define MAXWEIGHT 8#define TOTALITEMS 5struct packItem{ char name[100]; int value; int weight;};void main(){ struct packItem pck[]={{"lizi",450,4},{"Apple",570,5},{"Orange",225,2},{"Strawberry",110,1},{"Melo",670,6}};//PRintf("/n%s",pck[0].name); int items[MAXWEIGHT+1]; int values[MAXWEIGHT+1]; int tmp,tmp2; int i,j,k; for(k=0; k<MAXWEIGHT+1; k++){ items[k]=0; values[k]=0; } i=1; while(i<TOTALITEMS+1){ for(j=1; j<MAXWEIGHT+1; j++){ if(j<pck[i-1].weight){ continue; } tmp=j-pck[i-1].weight; if(values[tmp] + pck[i-1].value >= values[j]){ values[j] = values[tmp] + pck[i-1].value; items[j] = i; continue; } else{ continue; } } i++; } for(k=1; k<MAXWEIGHT+1; k++){ printf("/n%d", values[k]); } for(k=MAXWEIGHT; k>0; k=k-tmp2){ printf("/nPut%s ",pck[items[k]-1].name); printf(" %d ",pck[items[k]-1].weight); tmp2= pck[items[k]-1].weight; } system("pause");}

上一篇：Jenkins FindBugs Warnings 警告类型文档

下一篇：1049. Counting Ones (30)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注