数据结构与算法：动态规划中根据数据量猜解法

前言

这个说是算法竞赛里最重要的技巧也不为过。

一、打 怪 兽

#include<bits/stdc++.h>
using namespace std;//当money数据范围不大时，dp[i][j]为通过前i个怪兽，最多花j元钱的最大能力值
void solve1()
{int n;cin>>n;vector<int>power(n+1);vector<int>money(n+1);int sum=0;for(int i=1;i<=n;i++){cin>>power[i]>>money[i];sum+=money[i];}vector<vector<int>>dp(n+1,vector<int>(sum+1));for(int i=1;i<=n;i++){for(int j=0;j<=sum;j++){dp[i][j]=INT_MIN;//不贿赂if(dp[i-1][j]>=power[i]){dp[i][j]=dp[i-1][j];}//能贿赂且之前能通过if(j-money[i]>=0&&dp[i-1][j-money[i]]!=INT_MIN){dp[i][j]=max(dp[i][j],dp[i-1][j-money[i]]+power[i]);}}}//检查最后一行第一个能通过的答案for(int j=0;j<=sum;j++){if(dp[n][j]!=INT_MIN){cout<<j;return ;}}}//当power数据范围不大时，dp[i][j]为通过前i个怪兽，能力值正好为j的最小钱
//内存超限！！！
void solve2()
{int n;cin>>n;vector<int>power(n+1);vector<int>money(n+1);int sum=0;for(int i=1;i<=n;i++){cin>>power[i]>>money[i];sum+=power[i];}vector<vector<int>>dp(n+1,vector<int>(sum+1));//初始化for(int j=1;j<=sum;j++){dp[0][j]=INT_MAX;}for(int i=1;i<=n;i++){for(int j=0;j<=sum;j++){dp[i][j]=INT_MAX;//不贿赂if(j>=power[i]&&dp[i-1][j]!=INT_MAX){dp[i][j]=dp[i-1][j];}//贿赂if(j>=power[i]&&dp[i-1][j-power[i]]!=INT_MAX){dp[i][j]=min(dp[i][j],dp[i-1][j-power[i]]+money[i]);}}}int ans=INT_MAX;for(int j=0;j<=sum;j++){if(dp[n][j]!=INT_MAX){ans=min(ans,dp[n][j]);}}cout<<ans;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve1();return 0;
}</