hdu 2602 and poj 3624(01背包)

本文主要是介绍hdu 2602 and poj 3624(01背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包的模板题。

hdu2602代码：

#include<stdio.h>
#include<string.h>
const int MaxN = 1001;int max(int a, int b)
{return a > b ? a : b;
}int w[MaxN];
int v[MaxN];
int dp[MaxN];int main()
{int T;int N, V;scanf("%d", &T);while(T--){scanf("%d%d", &N, &V);for(int i = 1; i <= N; i++){scanf("%d", &w[i]);}for(int i = 1; i <= N; i++){scanf("%d", &v[i]);}memset(dp, 0, sizeof(dp));for(int i = 1; i <= N; i++){for(int l = V; l >= v[i]; l--){dp[l] = max(dp[l], dp[l - v[i]] + w[i]);}}printf("%d\n", dp[V]);}return 0;
}

poj3264：

#include<stdio.h>
#include<string.h>
const int MaxN = 3403;
const int MaxV = 12881;//debugint w[MaxN];
int d[MaxN];
int dp[MaxV];int max(int a, int b)
{return a>b?a:b;
}int main()
{int N, M;scanf("%d%d", &N, &M);for(int i = 1; i <= N; i++){scanf("%d%d", &w[i], &d[i]);}memset(dp, 0, sizeof(dp));for(int i = 1; i <= N; i++){for(int v = M; v >= w[i]; v--){dp[v] = max(dp[v], dp[v - w[i]] + d[i]);}}printf("%d\n", dp[M]);return 0;
}

这篇关于hdu 2602 and poj 3624(01背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---