分组背包

userId_undefined

klz

倔强青铜

2025-05-17 14:37:03

发布于：上海

2阅读
0回复
0点赞

分组背包:

1，通天之分组背包：
1：组数
2：重量
3：一组里的物品

for(int i=1;i<=t;i++)
		for(int j=v1;j>=0;j--)
            for(int k=0;k<v[i].size();k++)
                if(j>=v[i][k].w)dp[j] = max( dp[j] , dp[j-v[i][k].w] + v[i][k].c);

2，我爱运动鞋：
1：组数
2：每一组的物品
3，重量

for(int i=1;i<=k;i++){
	for(int w=0;w<v[i].size();w++){
		for(int j=m;j>=v[i][w].b;j--){
			//买多件
			if(dp[i][j-v[i][w].b] != -1) 
				dp[i][j] = max(dp[i][j],dp[i][j-v[i][w].b]+v[i][w].c);
				//只买一件
			if(dp[i-1][j-v[i][w].b] != -1)
				dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][w].b]+v[i][w].c);
		}
	}
}

因为我爱运动鞋中每个品牌都需要至少买一件，所以需要先遍历每组的物品，在遍历重量这样才能保证达到每组都可以至少选一件的目的

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论