首页 > 代码库 > 装箱问题（0-1背包）

装箱问题（0-1背包）

2024-07-17 16:31:46   224人阅读

有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

 

#include <iostream>#define MAX 12882using namespace std;struct node{    int w;}data[MAX];int dp[MAX],n,m;void Init(){    int i;    for(i=1;i<=n;i++)        scanf("%d",&data[i].w);}int GetMax(int a,int b){    if(a>b)        return a;    else        return b;}void Knapsack(){    int i,j;    for(i=0;i<=m;i++)    {        if(i>=data[n].w)            dp[i]=data[n].w;        else            dp[i]=0;    }    for(i=n-1;i>=1;i--)        for(j=m;j>=1;j--)        {            if(j>=data[i].w)            {                dp[j]=GetMax(dp[j],dp[j-data[i].w]+data[i].w);            }            else                break;        }}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        Init();        Knapsack();        printf("%d\n",dp[m]);    }    return 0;}

 


联系
我们