按DFS+dp做法,按理说砝码重量上限时100 * 20,但是dp从20000开始搜索后四个就会TLE。是题目的数据不够大吗?
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 20;
int n, m, res;
int weights[MAX_N];
bool dp[20001];
bool flag[MAX_N];
void dfs(int k, int cnt){
if (k == n && cnt != m){
return;
}
if (cnt == m){
fill(dp, dp + 20001, false);
dp[0] = true;
for (int i = 0 ; i < n ; i++){
if (flag[i]){
continue;
}
for (int j = 20000 ; j >= weights[i] ; j--){
dp[j] = dp[j] || dp[j - weights[i]];
}
}
int temp = 0;
for (int i = 20000 ; i > 0 ; i--){
if (dp[i]){
temp++;
}
}
res = max(res, temp);
}else{
dfs(k + 1, cnt);
flag[k] = true;
dfs(k + 1, cnt + 1);
flag[k] = false;
}
}
int main()
{
cin >> n >> m;
for (int i = 0 ; i < n ; i++){
scanf("%d", &weights[i]);
}
dfs(0, 0);
cout << res << endl;
}