一、问题描述

二、代码

#include<stdio.h>

int main()
{
    int n,m,d;
    int d_now=0;//当前总价值
    int w_now=0;//当前重量
    int w_min=9999;//最小重量
    scanf("%d %d %d",&n,&m,&d);
    int w[n+1][m+1];
    int c[n+1][m+1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&w[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&c[i][j]);
        }
    }
    int p[m+1];//存储各部件对应供应商编号
    int pmin[m+1];//存储最小重量对应供应商编号
    for(int i=1;i<=n;i++)
        p[i]=0;
    int t=1;//行
    int q=1;//列
    while(t>0)
    {
        if(d_now+c[t][q]>d)
        {
            if(q<m)                //下一个供应商
            q++;
            else                //上一个部件
            {
                t--;
                d_now-=c[t][p[t]];
                w_now-=w[t][p[t]];
                while(p[t]>=m)
                {
                    t--;
                    d_now-=c[t][p[t]];
                    w_now-=w[t][p[t]];
                    if(t<=0)
                        break;
                }
                q=p[t]+1;
            }
        }
        else
        {
            d_now+=c[t][q];
            w_now+=w[t][q];
            p[t]=q;
            if(t==n)//已到最后一个部件
            {
                if(w_now<w_min)
                {
                    for(int i=1;i<=n;i++)
                        pmin[i]=p[i];
                    w_min=w_now;
                }
                if(q<m)
                {
                    w_now-=w[t][q];
                    d_now-=c[t][q];
                    q++;
                }
                else
                {
                    d_now-=c[t][p[t]];
                    w_now-=w[t][p[t]];
                    t--;
                    d_now-=c[t][p[t]];
                    w_now-=w[t][p[t]];
                    while(p[t]>=m)
                    {
                        t--;
                        d_now-=c[t][p[t]];
                        w_now-=w[t][p[t]];
                        if(t<=0)
                            break;
                    }
                    q=p[t]+1;
                }
            }
            else//未到最后一个部件
            {
                t++;
                q=1;
            }
        }
    }
    printf("%d\n",w_min);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",pmin[i]);
    }
    return 0;
}

 三、结果

四、完整程序代码包

SuanFa5_3.rar-讲义文档类资源-CSDN下载算法（c++）——最小重量机器设计问题更多下载资源、学习资料请访问CSDN下载频道.https://download.csdn.net/download/lcf0000/55671041