做题感悟:开始做时感觉和FATE差不多,直接二维 01 背包写,但是必须要恰好选择 m 个这一点怎么也没想出怎么控制。
解题思路:二维 01 背包,但是要注意恰好选择 m 个 ,so ~ 初始化时要特别注意。
状态方程: dp [ i ][ j ] = max( dp[ i ][ j ] , dp [ i-1 ] [ j - v ] + w ) ;
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define lld __int64 const double PI = 3.1415926 ; const double esp = 1e-4 ; const int md= 2810778 ; const int INF = 99999999 ; const int MX = 1005 ; int n,m,C ; int dp[MX][MX] ; int main() { int Tx ; scanf("%d",&Tx) ; while(Tx--) { int v,w ; scanf("%d%d%d",&n,&m,&C) ; for(int i=0 ;i<=m ;i++) // 除了dp[0][0] 点 都初始化为 -INF for(int j=0 ;j<=C ;j++) dp[i][j]=-INF ; dp[0][0]=0 ; for(int t=0 ;t<n ;t++) { scanf("%d%d",&v,&w) ; for(int i=m ;i>=1 ;i--) for(int j=C ;j>=v ;j--) if(dp[i][j]<dp[i-1][j-v]+w) dp[i][j]=dp[i-1][j-v]+w ; } int max=0 ; for(int i=0 ;i<=C ;i++) // 在选择 m 件的前提下选择价值最大的 if(dp[m][i]>max) max=dp[m][i] ; printf("%d\n",max) ; } return 0 ; }