背包dp模板

01背包

for (int i=1; i<=n; i++) //物品
{
	for (int j=1; j<=V; j++) //容积 
    {    
        // 装得下 分为 1.装 2.不装
		if (j>=v[i]) dp[j] = max(tmp[j],tmp[j-v[i]]+v[i]);
		else dp[j] = tmp[j]; // 装不下第i个
	}
	for (int j=1; j<=V; j++) tmp[j] = dp[j]; //滚动数组
}

滚动数组

for (int i=1; i<=n; i++) //物品
{
	for (int j=V; j>=v[i]; j--) //容积 
    {    
		dp[j] = max(dp[j],dp[j-v[i]]+v[i]);
	}
}

无滚动数组 倒着遍历

完全背包

	for (int i=1; i<=m; i++) {
		for (int  j=1; j<=t; j++) {
			if (j<tim[i]) dp[j] = tmp[j];
			else dp[j] = max(tmp[j], dp[j-tim[i]]+val[i]);
		}
		for (int j=1; j<=t; j++) tmp[j] = dp[j];
	}

滚动数组

	for (int i=1; i<=m; i++) {
		for (int j=tim[i]; j<=t; j++) {
			dp[j] = max(dp[j], dp[j-tim[i]]+val[i]);
		}
	}

 无滚动数组 顺着遍历