问题描述:

    有n种重量和价值分别为wi, vi 的物品。从这些物品中挑选总重量不超过MaxValue的物品,求挑选物品价值总和的最大值。在这里,每种物品可以挑选任意多件。

限制条件:

    1 <= n <= 100 ,    1 <= wi, vi <= 100 ,     1 <= MaxValue <= 10000

输入:

3

3 4

4 5

2 3

7

输出:

10


#include <cstdio>
#include <algorithm>
#define MAXN 100
using namespace std;
void solve();	/* 此函数是主函数中递推方法的简化版*/

int n, MaxValue;
int w[MAXN+1], v[MAXN+1];
int dp[MAXN+1][MAXN+1];
int main()
{
	scanf("%d", &n );
	for( int i=0; i<n; i++ )
		scanf("%d%d", &w[i], &v[i] );
	scanf("%d", &MaxValue );

	for( int i=0; i<n; i++ )
	{
		for( int j=0; j<=MaxValue; j++ )
		{
			for( int k=0; k*w[i] <= j; k++ )	// 利用k的累加性,可以找到当前物品选的最大数量
				dp[i+1][j] = max( dp[i+1][j], dp[i][j -k*w[i]] + k*w[i] );
				// max() 选出的是不选当前物品与选当前物品k个中,价值较大的一个
				// dp[i][j -k*w[i]] + k*w[i] 表示丛前i种物品中挑选出总重量不超过j -k*w[i]的总价值得最大值
				// 且加上当前能选的物品的数量的最大值
		}
	}
	printf("%d\n", dp[n][MaxValue] );


	return 0;
}

/* 在dp[i+1][j]的计算中选择 k(k>=1)个的情况,与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是相同的
   所以,dp[i+1][j]的递推中k>=1部分的计算在dp[i+1][j-w[i]]的计算中完成了 */
void solve()
{
	for( int i=0; i<n; i++ )
	{
		for( int j=0; j<=MaxValue; j++ )
		{
			if( j <w[i] )	// 如果不能选则前i+1个与前i个情况相同
				dp[i+1][j] = dp[i][j];
			else
				dp[i+1][j] = max( dp[i][j], dp[i+1][j-w[i]] + v[i] );
		}
	}
	printf("%d\n", dp[n][MaxValue] );
}