做题感悟：这题比赛时想了好久才做出来，赛后一想其实就是 01 背包一下，记录各个体积的最优值就可以了，比赛时想多了。
解题思路：
我直接开的二维数组 dp[ i ] [ j ] 代表达到体积 i ,做了 j 道题所达到的最优状态 ： dp[ i ] [ j ] = { dp [ i - v ] [ j - 1 ] } 的最优值 ，其实就是二维的背包 。
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std ;
#define INT long long int
const int INF = 0x3f3f3f3f ;
const int MX = 1000 + 10 ;
int C ,n ;
int dp[2][MX][55] ;
struct node
{
int v ,w ;
}T[MX] ;
bool cmp(node a, node b)
{
if(a.v == b.v) return a.w > b.w ;
else
return a.v < b.v ;
}
void input()
{
scanf("%d%d" ,&C ,&n) ;
for(int i = 0 ;i < n ; ++i)
scanf("%d" ,&T[i].v) ;
for(int i = 0 ;i < n ; ++i)
scanf("%d" ,&T[i].w) ;
}
int main()
{
//freopen("input.txt" ,"r" ,stdin) ;
int Tx ;
scanf("%d" ,&Tx) ;
while(Tx--)
{
input() ;
int ans = 0 ,num = 0 ,Wx = INF ;
sort(T ,T+n ,cmp) ;
memset(dp[0] ,-1 ,sizeof(dp[0])) ;
memset(dp[1] ,0 ,sizeof(dp[1])) ;
dp[0][0][0] = 0 ;
for(int t = 1 ;t <= n ; ++t)
for(int j = C ;j >= T[t-1].v ; --j)
for(int i = t ;i >= 1 ; --i)
if(dp[0][j-T[t-1].v][i-1] != -1)
{
int v = T[t-1].v ;
int w = T[t-1].w ;
if(dp[0][j][i] < dp[0][j-v][i-1] + w)
{
dp[0][j][i] = dp[0][j-v][i-1] + w ;
dp[1][j][i] = dp[1][j-v][i-1] + j ;
}
else if(dp[0][j][i] == dp[0][j-v][i-1] + w && dp[1][j][i] > dp[1][j-v][i-1] + j)
{
dp[0][j][i] = dp[0][j-v][i-1] + w ;
dp[1][j][i] = dp[1][j-v][i-1] + j ;
}
if(dp[0][j][i] > ans || (dp[0][j][i] == ans && i > num) || (dp[0][j][i] == ans && i == num && Wx > dp[1][j][i]))
{
ans = dp[0][j][i] ;
num = i ;
Wx = dp[1][j][i] ;
}
}
if(Wx != INF)
cout<<ans<<" "<<num<<" "<<Wx<<endl ;
else cout<<"0 0 0"<<endl ;
}
return 0 ;
}