首页 > 代码库 > 南阳OJ 背包问题

南阳OJ 背包问题

??

/*背包问题
时间限制:3000 ms  |  内存限制:65535 KB
难度:3
描写叙述 如今有非常多物品(它们是能够切割的),我们知道它们每一个物品的单位重量的价值v和
重量w(1<=v,w<=10);假设给你一个背包它能容纳的重量为m(10<=m<=20),
你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。
输入第一行输入一个正整数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*/

<span style="font-size:18px;">#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
struct pack{  
    int v;//单位价值   
    int w;//重量   
    int total; //总价值   
}bao[10];  
int cmp( const void *a ,const void *b){  
    return (*(pack *)b).v - (*(pack *)a).v;//这是qsort函数。

} int main(){ int n,s,i,j; int vsum,wsum,m; scanf("%d",&n); while(n--){// 測试组数 memset(bao,0,sizeof(bao)); //不要忘记每次循环都要初始化数组!

!。 scanf("%d%d",&s,&m);// 物品数量,背包最大载重 for(i=0;i<s;i++){ scanf("%d%d",&bao[i].v,&bao[i].w); bao[i].total=bao[i].w*bao[i].v; }//计算每一个物品总价值 qsort(bao,10,sizeof(bao[0]),cmp); wsum=0; vsum=0; for(i=0;i<s;i++){ if(m>=(wsum+bao[i].w)){ //整放物品 vsum+=bao[i].total; wsum+=bao[i].w; } else if(m<(wsum+bao[i].w)&&m>=wsum){ //假设不能整放物品,就切割开放 vsum+=(m-wsum)*bao[i].v; break; } } printf("%d\n",vsum); } return 0; } </span>



南阳OJ 背包问题