首页 > 代码库 > 完全背包问题(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))