Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506066
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-09-19 09:21:34

/**
Description

设有一个背包可以放入物品的重量为s,现有n件物品,重量分别为w[0],w[1],...,[n-1]。
问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s。
如果存在一种符合上述要求的选择,则称此背包问题有解;否则称此背包问题无解。


数据输入:

第一行:测试集合个数m。
第二行:第一个测试用例的s值。
第三行:第一个测试用例的物品数量n。
第四行:第一个测试用例的n件物品的重量,中间用空格分开。
第五行:第二个测试用例的s值。
第六行:第二个测试用例的物品数量n。
第七行:第二个测试用例的n件物品的重量,中间用空格分开。
………
第2m行:第m个测试用例的s值。
第2m+1行:第m个测试用例的物品数量n。
第2m+2行:第m个测试用例n件物品的重量,中间用空格分开。


数据输出:

第一行到第m行:分别输出是否成功,如果可以放入和为s的物品,则输出1,否则输出0。

Sample Input

2
21
5
2 5 9 11 13
13
4
2 3 5 8


Sample Output

0
1
*/


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX 100

  4. typedef struct
  5. {
  6.     int *base; //指向栈底
  7.     int *top; //指向栈顶的后一个
  8.     int sum; //计算入栈的各数之和
  9. } stack;

  10. void init(stack *s);
  11. void push(stack *s,int data);
  12. void pop(stack *s);

  13. int main()
  14. {
  15.     /**
  16.     cases个测试用例、背包容量为capacity、n为物品数目、weight表示每个物品的重量
  17.     */
  18.     int cases,capacity,n,weight[MAX],i,j;

  19.     scanf("%d",&cases);

  20.     stack *s = (stack*)malloc(sizeof(stack));

  21.     while(cases--)
  22.     {
  23.         scanf("%d",&capacity);
  24.         scanf("%d",&n);

  25.         init(s);

  26.         for(i=0; i<n; i++)
  27.         {
  28.             scanf("%d",&weight[i]);
  29.         }

  30.         for(i=0; i<n; i++)
  31.         {
  32.             for(j=i; j<n; j++)
  33.             {
  34.                 if(weight[j] + s->sum <= capacity) //判断是不是符合入栈条件
  35.                 {
  36.                     push(s,weight[j]);
  37.                     if(s->sum == capacity)
  38.                     {
  39.                         printf("1\n");
  40.                         break;
  41.                     }
  42.                 }
  43.             }

  44.             if(s->sum == capacity)
  45.             {
  46.                 break;
  47.             }
  48.             init(s);
  49.         }

  50.         if(n == i) //能满足这个条件必定有s->sum != capacity
  51.         {
  52.             printf("0\n");
  53.         }

  54.     }
  55.     return 0;
  56. }



  57. //初始化栈
  58. void init(stack *s)
  59. {
  60.     s->base = s->top = (int*)malloc(MAX * sizeof(int));
  61.     s->sum = 0;
  62. }

  63. //入栈操作
  64. void push(stack *s,int data)
  65. {
  66.     *(s->top) = data; //栈顶元素赋值为data
  67.     (s->top)++; //始终指向栈顶元素的下一个元素位置
  68.     s->sum += data; //和要发生变化
  69. }

  70. //出栈操作

  71. void pop(stack *s)
  72. {
  73.     (s->top)--;
  74.     s->sum -= *(s->top);
  75. }

阅读(596) | 评论(0) | 转发(0) |
0

上一篇:24点问题

下一篇:无向图的关节点

给主人留下些什么吧!~~