首页 > 代码库 > 背包问题

背包问题

2024-08-05 18:40:13   221人阅读

描述
现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值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

#include<iostream>
using namespace std;
int main()
{
	int n,s,m,v[11],w[11],sum,t,i,j;//v[11]表示价值，w[11]表示重量
	cin>>n;
	while(n--)
	{
		sum=0;
		t=0;
		cin>>s>>m;
		for(i=0;i<s;i++)
			cin>>v[i]>>w[i];
		for(i=0;i<s;i++)
		{
			for(j=0;j<s-1-i;j++)
			{
				if(v[j+1]>v[j])//按物品的价值从大到小的排序
				{
					swap(v[j],v[j+1]);
					swap(w[j],w[j+1]);
				}
			}
		}
		for(i=0;i<s;i++)
		{
			sum+=w[i];
			if(sum>m)
				break;
		}
		if(i==0)
			cout<<m*v[0]<<endl;
		else
		{
			for(j=0;j<i;j++)
			{
				t+=v[j]*w[j];
				m-=w[j];
			}
			cout<<t+m*v[i]<<endl;
		}
	}
	return 0;
}


背包问题


联系
我们