加限制条件的0-1背包
发布时间：2010/7/26 10:32:26 来源：城市学习网 编辑：ziteng
1 #include<stdlib.h>
2 #include<stdio.h>
3 #include<string.h>
4 int n,m,k,p[101],max=0,v[101];
5 int br[11][101],sum[11] ;
6 long f[11][10001];
7
8 int main(){
9 int i,j,x,i1;
10 while(scanf("%d%d%d",&n,&m,&k)!=EOF)
11 {
12 memset(sum,0,sizeof(sum));
13 for(i=1;i<=n;i++)
14 {
15 scanf("%d%d%d",&x,&p[i],&v[i]);
16 br[x][++sum[x]]=i;
17 }
18 for(i=1;i<=k;i++)
19 for(j=1;j<=m;j++)
20 f[i][j]=-1;
21 for(j=1;j<=m;j++)
22 f[0][j]=0;
23 for(i=1;i<=k;i++)---------表示品牌编号
24 for(i1=1;i1<=sum[i];i1++)--------表示i品牌下的产品编号
25 for(j=m;j>=1;j--)-------------表示可以花费的钱，注意要倒写
26 {
27 if(j>=p[br[i][i1]])
28 {
29 if(f[i][j-p[br[i][i1]]]!=-1&&f[i][j]<f[i][j-p[br[i][i1]]]+v[br[i][i1]])
30 f[i][j]=f[i][j-p[br[i][i1]]]+v[br[i][i1]];
31 if(f[i-1][j-p[br[i][i1]]]!=-1&&f[i][j]<f[i-1][j-p[br[i][i1]]]+v[br[i][i1]])
32 f[i][j]=f[i-1][j-p[br[i][i1]]]+v[br[i][i1]];
33 }
34 } [NextPage] 35 if(f[k][m]<0)printf("Impossible\n");
36 else
37 printf("%d\n",f[k][m]);
38 }
39 return 0;
40 }
程序思想：f[i][j]代表用j的价钱买前i个品牌可以得到的最大价值数。
赋初值：见18到22行
状态转移：f[i][j]可以经过三种状态得到----
f[i][j]，f[i-1][j-p[br[i][i1]]]+v[br[i][i1]]，f[i][j-p[br[i][i1]]]+v[br[i][i1]]
br[i][i1]代表第i种品牌的第i1个产品，p[]是某产品的价格，v[]是某产品的价值。
意思是，当放到第i个品牌的第i1个产品时，它的状态等于不放第i1个产品，而放i1以前的i类品牌中的某些产品（f[i][j]），放i类品牌的第i1个产品，而不放i的其他产品（f[i-1][j-p[br[i][i1]]]+v[br[i][i1]]），放i类的第i1个产品，同时也放i 类中i1以前的某些产品 （f[i][j-p[br[i][i1]]]+v[br[i][i1]] ） 。
几个问题：
1.如何保证每一类品牌至少放一件产品？
答：首先看循环:
for(i=1;i<=k;i++)
for(i1=1;i1<=sum[i];i1++)
for(j=m;j>=1;j--)
if(j>=p[br[i][i1]])----限制条件
在某一状态存在的情况下（不等于-1），找出三种状态中最大的，赋值给f[i][j] .由于开始时所有f[i][j](i!=0)都为-1，所以i=1更新时一定会从f[0][]开始，而此时就可保证当i=1时，f[i][j]中所有值不为-1的状态一定装了品牌1的某个物品。而当i>1时，要想得到最初的f[i][j],一定是从已经放有前i-1个品牌的某个状态得到的，而更新最初的f[i][j] 也一定会用到i品牌的某个产品(都可由状态转移方程可知)。
总之，保证每一类品牌 至少放一件产品是通过赋初值，条件判断，状态转移三方面实现的。
2.如何抱证每个产品只放一次？
答： 注意循环安排顺序：将对某一品牌产品编号的循环放在对限制总钱数的循环之前 。
