博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ppt 例题8 多重背包2
阅读量:5141 次
发布时间:2019-06-13

本文共 688 字,大约阅读时间需要 2 分钟。

#include <stdio.h>

#include <string.h>
int dp[60001];
void f(int maxv,int n,int c[ ],int v[ ])
//最大可能价值、 物品种类、物品数量、物品价值
{   int i,j,k,t;
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for ( i = 1; i <=n; i++) //物品种类
        for (j = maxv; j>=0; j--) //必须从背包容量向下循环
            if (dp[j])
            {  
                for ( k = 1; k <= c[i]; k++) //物品数量循环
                     dp[t=j  +k*v[i]] = 1;
            }
}

int main()

{   int i,sum;
    int c[7],v[7];  //物品的数量与价值
    while (1)
    {   sum = 0;
        for (i = 1; i <= 6; i++) //输入6种物品的个数
        {   scanf("%d",&c[i]);   v[i]=i;  sum += c[i]*v[i];  }
        if (sum==0)  break;
        if (sum%2)  { printf("Can't\n");   continue;  }
        f(sum,6,c,v);     //调用模版函数f()
        if (dp[sum/2]==1) printf("Can\n");
        else printf("Can't\n");
    }
    return 0;
}

转载于:https://www.cnblogs.com/2014acm/p/3919086.html

你可能感兴趣的文章
软件工程课堂作业
查看>>
OpenFire 的安装和配置
查看>>
web.config详解
查看>>
ZJOI2018游记Round1
查看>>
侧边栏广告和回到顶部
查看>>
https://blog.csdn.net/u012106306/article/details/80760744
查看>>
ios应用版本号设置规则
查看>>
海上孤独的帆
查看>>
error: more than one device and emulator 问题解决
查看>>
Java基础:容器
查看>>
YUV摘要格式
查看>>
【方法2】删除Map中Value反复的记录,而且仅仅保留Key最小的那条记录
查看>>
C# CheckedListBox控件的使用方法
查看>>
【HDOJ】2007平方和与立方和
查看>>
js中const,var,let区别
查看>>
SharePoint自定义程序页面部署 不用重启IIS
查看>>
2014-11-30-2333-Java-数组
查看>>
Nginx 自动补全url地址补全最后的斜线
查看>>
【SQL Server 2008 安装全过程】
查看>>
xml的解析及案例的分析和分享
查看>>