题目描述
题意:输入t,再输入t组样例,每组样例输入三个数,n,v,k,接下来一行输入n个数代表物体质量,再下一行输入n个数代表物体体积,输出v体积下的第k个最优解。
算法1
(01背包) $O(n*m*k)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define dbgfull(x) cerr << #x << " = " << x << " (line " << __LINE__ << ")"<<endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(x) cerr << #x " = " << (x) << endl
#define endl "\n"
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
int f[1005][35];
int w[105],v[105];
int a[35],b[35];
void solve(){
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; ++i) cin >> w[i];
for(int i = 1 ; i <= n ; ++i) cin >> v[i];
memset(f,0,sizeof(f));
for(int i = 1 ; i <= n ; ++i){
for(int j = m ; j >= v[i] ; --j){
//a中存不选当前物品的总价值
//b中存选择当前物品的总价值
for(int l = 1 ; l <= k ; ++l){
a[l] = f[j][l];
b[l] = f[j - v[i]][l] + w[i];
}
//处理边界
a[k + 1] = b[k + 1] = -1;
//归并a,b数组
for(int ca = 1,cb = 1,cur = 1 ; (ca <= k || cb <= k ) && cur <= k ;){
//用较大的数更新第cur大数
if(a[ca] > b[cb]) f[j][cur] = a[ca++];
else f[j][cur] = b[cb++];
//若当前数和前一个不同才将排名+1
if(f[j][cur] != f[j][cur - 1]) cur++;
}
}
}
cout << f[m][k] << endl;
}
signed main(){
IOS;
int tt;
cin >> tt;
while(tt--)
solve();
return 0;
}