枚举子集(30pts)

观察题目范围 有30%的数据$m\leq 10$,所以可以用枚举子集的方式枚举所有情况得到30分

时间复杂度 $O(n2^n)$

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N],w[N];
int main()
{
	int V,n;
	cin>>V>>n;
	for(int i=0;i<n;i++) //获取每株草药的时间和价值 
	{
		cin>>v[i]>>w[i];
	}
	int ans=0;
	for(int i=0;i<1<<n;i++) //依次枚举每种选择 
	{
		int sw=0,sv=0; //初始化 
		for(int j=0;j<n;j++) //枚举当前选择的每株草药 
		{
			if(i>>j&1) //选择了当前草药 
			{
				sv+=v[j],sw+=w[j];
			}
		}
		if(sv<=V) //选择的草药的总时间小于等于给定时间 
		{
			ans=max(ans,sw); //尝试更新答案 
		}
	}
	cout<<ans;
    return 0;
}

动态规划

观察数据 $m \leq 100,T \leq 1000$,那么可以使用01背包解决此问题

时间复杂度$(Onm)$

二维版本

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010;
int f[N][M]; //f[i][j]表示在前i个物品中选，体积不超过j的最大价值 
int v[N],w[N]; //v[i]表示第i个物品的体积 w[i]表示第i个物品的价值 
int main()
{
    int V,n;//V表示背包的体积,n表示物体的个数
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];//获取第i个物品的体积和价值 
    } 
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=V;j++)
        {
            f[i][j]=f[i-1][j];//不选第i个物品
            if(j>=v[i])
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
                //保留最大值  不选   选 
            } 
        }
    }
    cout<<f[n][V];
    return 0;
}

一维版本

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010;
int f[M]; //f[i][j]表示在前i个物品中选，体积不超过j的最大价值 
int main()
{
    int V,n;//V表示背包的体积,n表示物体的个数
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=V;j>=v;j--)
        {
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[V];
    return 0;
}