2 条题解
-
1
- #include <bits/stdc++.h> using namespace std; const int N = 201; int mem[N][N]; int v[N], w[N]; int n, m;//n是物品，m是重量 int dfs(int x, int spv) { if(mem[x][spv])return mem[x][spv]; int sum=0; if(x>n)return sum =0; if(spv<v[x])sum=dfs(x+1,spv); else if(spv>=v[x]){ sum=max(dfs(x+1,spv),dfs(x+1,spv-v[x])+w[x]); } mem[x][spv]=sum; return sum; } int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } memset(mem, 0, sizeof mem); int ans = dfs(1, m); cout << ans; return 0; }
