1651 - 珍惜现在，感恩生活

1
42 6
10 1 15
19 79 5
6 65 3
8 82 6
16 92 2
17 28 3

441

Hint

	 多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程： 


	              f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 


	这里同样转换为01背包： 


	普通的转换对于数量较多时，则可能会超时，可以转换成二进制（暂时不了解，所以先不讲）  对于普通的。就是多了一个中间的循环，把j=0~bag[i]，表示把第i中背包从取0件枚举到取bag[i]

Solution C

#include <stdio.h>
#include <string.h>
#define maxc 100
#define maxv 1000
int dp[maxv]={0};
int v[maxc]={0};
int p[maxc]={0};
int c[maxc]={0};
int max(int x,int y){
	return x>y?x:y;
}
int main()
{
	int i,j,k,n,m,nn,e;
	scanf("%d",&nn);
	for(e=0;e<nn;e++){
		scanf("%d%d",&m,&n);
		memset(dp,0,sizeof(dp));
		
		for(i=0;i<n;i++){
			scanf("%d%d%d",&v[i],&p[i],&c[i]);
		}
		for(i=0;i<n;i++){
			for(j=m;j>=0;j--){
			for(k=0;k<=c[i];k++){
				if(j-k*v[i]>=0){
					dp[j]=max(dp[j],dp[j-k*v[i]]+p[i]*k);
				}
			}
			}
		}
		printf("%d\n",dp[m]);
	}
	return 0;
}

Solution C++

#include <stdio.h>
int run()
{
	int i,j,a[111],b[111],c[111],n,m,d[111][111],k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(i=0;i<=m;i++)
		for(j=0;j<=n;j++)
			d[i][j]=0;
	for(i=0;i<m;i++)
		for(j=0;j<=n;j++)
			for(k=0;k<=c[i+1];k++)
				if((j+k*a[i+1]<=n)&&(d[i+1][j+k*a[i+1]]<d[i][j]+k*b[i+1]))
					d[i+1][j+k*a[i+1]]=d[i][j]+k*b[i+1]; 
	j=0;
	for(i=0;i<=n;i++)
		if(d[m][i]>j)
			j=d[m][i];
	printf("%d\n",j);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t!=0)
	{
		t--;
		run();
	}
	return 0;
}