若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2244: 背包问题(栈和队列)

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,288

题目描述

设有n件物品,重量分别为w1,w2,w3,…,wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能,则背包问题有解,否则无解。

输入

5 100
77 92

22 22

29 87

50 46

99 90

输出

133

样例输入

8 200
79 83
58 14
86 54
11 79
28 72
62 52
15 48
68 62 

样例输出

334

参考代码

#include<stdio.h>
#include<memory.h>
#define MAX 100
int weight[MAX],value[MAX],n,t,sum,visit[MAX];
void dfs(int w,int v,int k) 
{
    int i;
    if(v&&w<t)
            if(v>sum)
                sum=v;
    if(k==n)
            return;
    for (i=0;i<n;i++)
            if(!visit[i]) 
    {
        visit[i]=1;
        if(w+weight[i]<=t)
                        dfs(w+weight[i],v+value[i],k+1);
        visit[i]=0;
    }
}
int main() 
{
    int i;
    scanf("%d %d",&n,&t);
    sum=0;
    memset(visit,0,sizeof(visit));
    for (i=0;i<n;i++)
            scanf("%d %d",&weight[i],&value[i]);
    dfs(0,0,0);
    printf("%dn",sum);
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist