RNQOJ 98 逃亡的准备

http://www.rqnoj.cn/Problem_98.html

裸的多重背包

#include
#include
#include
using namespace std;
int N, V;
const int MAXV = 1 << 9;
int f[MAXV];void ZeroOnePack( int f[], int C, int W)
{int v;for( v = V; v >= C; v --)f[v] = max( f[v], f[v - C] + W);
}void CompletePack( int f[], int C, int W)
{int v;for( v = C; v <= V; v ++)f[v] = max( f[v], f[v - C] + W);
}void MultiplePack( int f[], int C, int W, int M)
{int k = 1;if( C * M >= V){CompletePack( f, C, W);return;}while( k < M){ZeroOnePack(f, C * k, W * k);M = M - k;k <<= 1;}ZeroOnePack( f, C * M, W * M);
}int main()
{int m, w, s;while( scanf( "%d%d", &N, &V) == 2){memset( f, 0, sizeof (int) * (V + 1));for( int i = 1; i <= N; i ++){scanf( "%d%d%d", &m, &w, &s);MultiplePack( f, w, s, m);}printf( "%d\n", f[V]);}return 0;
}

转载于:https://www.cnblogs.com/Yu2012/archive/2012/07/20/2601545.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！