三维背包,一个60一个100 有啥区别
查看原帖
三维背包,一个60一个100 有啥区别
394113
zly1783598949楼主2021/9/27 20:57
#include <bits/stdc++.h>
using namespace std;

int n,m,t;
int c1[101],c2[101]; //两种开销 
int dp[101][201][201]; //前i个,花费不超过j,时间不超过k时最值

int main()
{
	cin >> n >> m >> t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&c1[i],&c2[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=c1[i];j--)
		{
			for(int k=t;k>=c2[i];k--)
				dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-c1[i]][k-c2[i]] + 1);
		}
	}
	cout << dp[n][m][t] <<endl;
	return 0;
}

以上60分

#include <bits/stdc++.h>
using namespace std;

int n,m,t;
int c1[101],c2[101]; //两种开销 
int dp[101][201][201]; //前i个,花费不超过j,时间不超过k时最值

int main()
{
	cin >> n >> m >> t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&c1[i],&c2[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=t;k>=0;k--)
			{
				if(j >= c1[i] && k >= c2[i])
					dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-c1[i]][k-c2[i]] + 1);
				else dp[i][j][k] = dp[i-1][j][k];
			}
				
		}
	}
	cout << dp[n][m][t] <<endl;
	return 0;
}

100分

2021/9/27 20:57
加载中...