首页 > 代码库 > 完全背包问题(O(NV∑(V/Ci))
完全背包问题(O(NV∑(V/Ci))
背包问题最简单最粗暴的方法代码练习:
#include<stdio.h>//#define MIN -999999struct item//储存物品信息{ int value,weigh;//价值和重量};int main(){ int item_all,W_max;//item_all表示物体总数 W_max表示背包容量 struct item G[100]; printf("物品总数 最大质量\n"); scanf("%d%d",&item_all,&W_max); int i; printf("G[i].value G[i].weigh\n"); for(i=1;i<=item_all;i++) scanf("%d%d",&G[i].value,&G[i].weigh); int F[100]={0};//记录过程中的最大// for(i=1;i<=W_max;i++) // F[i]=MIN; int v,k; for(i=1;i<=item_all;i++){//分别表示i个物品放或者不放入背包 for(v=W_max;v>=G[i].weigh;v--){//分别表示最大容量为v的背包 //F[v]=max{F[v],F[v-G[i].weigh*k]-G[i].value*k} for(k=1;k<=W_max/G[i].weigh;k++) if(v-G[i].weigh*k>=0){//判断是否超过了背包容量 int temp=F[v-G[i].weigh*k]+G[i].value*k; if(temp>F[v]) F[v]=temp; } } int x; for(x=0;x<=W_max;x++) printf("F[%d]=%-3d",x,F[x]); printf("\n"); } printf("F[W_max}=%d\n",F[W_max]); return 0;}
测试数据:
完全背包问题(O(NV∑(V/Ci))
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。