acm 背包问题

╰半夏微凉° 2022-05-11 12:22 165阅读 0赞

> ## 背包问题 ##
> 
> 时间限制：3000 ms  |  内存限制：65535 KB
> 
> 难度：3
> 
> 输入
> 
> 第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；  
> 随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。
> 
> 输出
> 
> 输出每组测试数据中背包内的物品的价值和，每次输出占一行。
> 
> 样例输入
> 
>     1
>     3 15
>     5 10
>     2 8
>     3 9
> 
> 样例输出
> 
>     65
> 
> 描述
> 
> 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

> \#include<stdio.h>  
> int a\[10\],b\[10\];
> 
> //定义函数，返回一个整型数组中最大值的下标   
> int findMax(int ac\[10\],int n)\{  
>     int index = 0;  
>     int max = 0;  
>     for(int i = 0; i < n; i++)  
>     \{  
>         if(ac\[i\] > max)\{  
>             max = ac\[i\];  
>             index = i;  
>         \}  
>     \}  
>  return index;  
> \}
> 
> int main()  
> \{  
>     int n,s,m,max,sum;  
>     scanf("%d",&n);  
>     while(n--)  
>     \{      
>         //用于存储总价值   
>         sum = 0;   
>         scanf("%d%d",&s,&m);  
>         //遍历存取数据，a数组存单位重量的价值，b数组相应的下标位置存重量   
>         for(int i = 0; i < s; i++)  
>         \{  
>             scanf("%d %d",&a\[i\],&b\[i\]);  
>         \}  
>           
>     for(int j = 0; j < s; j++)  
>     \{  
>         //得到 单位重量的价值最高的下标   
>         max = findMax(a,s);  
>         //如果 当前单位重量最高的重量大于背包容纳总质量，则将背包装满，并结束循环   
>         if(b\[max\] >= m)  
>         \{  
>             sum = sum + a\[max\] \* m;  
>             break;  
>         \}  
>         else \{  
>             //将该物品装完   
>             sum = sum + a\[max\] \* b\[max\];  
>             //因为已经没有该物品，所以将该物品的价值定位0   
>             a\[max\] = 0;  
>             //重新选取 单位重量的价值最高的下标   
>             m = m - b\[max\];  
>         \}   
>     \}  
>     printf("%d\\n",sum);  
>     \}  
>     return 0;  
> \}