首页 > 代码库 > ppt 例题8 多重背包
ppt 例题8 多重背包
#include <stdio.h>
#include <string.h>
int dp[60001];
void f(int maxv,int n,int c[ ],int v[ ])
//最大可能价值、 物品种类、物品数量、物品价值
{ int i,j,k,t;
memset(dp,0,sizeof(dp));
dp[0] = 1;
for ( i = 1; i <=n; i++) //物品种类 // 物品种类 从1开始
for (j = maxv; j>=0; j--) //必须从背包容量向下循环 //j 从最大的 开始
if (dp[j])
{ t = j; // t 的 初值为 j
for ( k = 1; k <= c[i]; k++) //物品数量循环
dp[t=t+v[i]] = 1; // t 也会变化
}
}
int main()
{ int i,sum;
int c[7],v[7]; //物品的数量与价值
while (1)
{ sum = 0;
for (i = 1; i <= 6; i++) //输入6种物品的个数
{ scanf("%d",&c[i]); v[i]=i; sum += c[i]*v[i]; }
if (sum==0) break;
if (sum%2) { printf("Can‘t\n"); continue; }
f(sum,6,c,v); //调用模版函数f()
if (dp[sum/2]==1) printf("Can\n");
else printf("Can‘t\n");
}
return 0;
}