题干:

有两种物品,k分别为k1,k2,有大小各不一的这两种物品若干,放入容量为c的背包中,能获得求最大的值。放的顺序会影响结果。每次放入一物品,其获得的值都可以用v=kr计算,r表示放入后背包剩下的容量。

有两种物品分别为n,m个,每种物品对应价值k1,k2。有一个容量为c的背包,每次将一个物品放入背包所获取的价值为k1/k2*放入物品后的剩余体积。求问所获取的最大价值。

解题报告:

   首先同组内一定是优先选容量小的,所以先对组内排序。然后考虑选中的次序,考虑dp。

   这题是类型不相同的背包,dp[i][j]代表第一组前i个,和第二组前j个可以组成的最大价值。

   注意取maxx的时候别忘了考虑只选择一种的。即前几个初始化的for循环,也需要取max。

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX],b[MAX]; 
ll dp[2005][2005],suma[MAX],sumb[MAX];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		ll k1,k2,c,n,m;
		scanf("%lld%lld%lld",&k1,&k2,&c);
		scanf("%lld%lld",&n,&m);
		for(int i = 1; i<=n; i++) {
			scanf("%lld",a+i);
		}
		for(int i = 1; i<=m; i++) {
			scanf("%lld",b+i);
		}
		sort(a+1,a+n+1);
		sort(b+1,b+m+1);
		for(int i = 1; i<=n; i++) suma[i] = a[i] + suma[i-1];
		for(int i = 1; i<=m; i++) sumb[i] = b[i] + sumb[i-1]; 
		ll maxx = 0;
		dp[0][0]=0;
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) dp[i][j]=0;
		}
		for(int i = 1; i<=n; i++) {
			if(c-suma[i] < 0) break;
			dp[i][0]=dp[i-1][0] + k1*(c-suma[i]);
			maxx = max(maxx,dp[i][0]);
		}
		for(int i = 1; i<=m; i++) {
			if(c-sumb[i] < 0) break;
			dp[0][i]=dp[0][i-1] + k2*(c-sumb[i]);	
			maxx = max(maxx,dp[0][i]);	
		}
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				if(suma[i] + sumb[j] > c) break;
				dp[i][j] = max(dp[i-1][j] + k1*(c - suma[i]-sumb[j]),dp[i][j-1] + k2*(c - suma[i]-sumb[j])) ;
				maxx = max(maxx,dp[i][j]);
			}
		}
		printf("%lld\n",maxx);
	}
	return 0 ;
}