本文主要是介绍ZOJ 3703 Happy Programming Contest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：这题比赛时想了好久才做出来，赛后一想其实就是 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 ;elsereturn 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 ;
}
这篇关于ZOJ 3703 Happy Programming Contest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
