POJ-3093___Margaritas on the River Walk —— 01背包的变异

本文主要是介绍POJ-3093___Margaritas on the River Walk —— 01背包的变异，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

题目大意：

    多组样例，在这里我们假设有$n$个物品，容量为$m$的背包，问有多少种方案，使得剩下的任意一件物品都装不进背包。。。。。。

解题思路：

    假如在剩下的物品中，体积最小为$w$的物品装不进背包，那么很明显所有背包中体积小于$w$的都被放进去了，依此思路，我们给所有背包排个序，然后依次枚举每个背包，将这个背包当做剩下的体积最小的背包，所以，当枚举到第$i$个背包时，第$1...i-1$件背包都被放进去了。
    设第$i$个背包的体积为$w[i]$，前$i$个物品的体积和为$sum[i]$

    当枚举到$i$时，由于第$1...i-1$件物品已被放入背包，所以背包剩余容量为$m-sum[i-1]$，这时，要使得第$i$件物品放不进去，就要用第$i+1...n$的物品装满剩余容积为$m-sum[i-1]-w[i]+1$  ~  $m-sum[i-1]$的背包，这样使得第$i$件物品恰好放不进背包（背包剩余容量小于$w[i]$）。

   加下来考虑枚举问题。

    $①$从$1$顺序枚举到$n$，则第一次对$（2，n）$做$01$背包，第二次对$（3，n）$做$01$背包$......$时间复杂度为 $O(n^{2}m)$
    $②$从$n$逆序枚举到$1$，则我们需要对$（i+1，n）$做$01$背包，对$（i，n）$做$01$背包，对$（i-1，n）$做$01$背包，会发现，每次做$01$背包都是放入了$1$个物品，显然我们可以对此进行优化，在上一次做完背包之后，把第$i$件物品放入上一次做完的背包，就得到了我们需要的状态，这样从头到尾只做了一次背包。时间复杂度为 $O(nm)$

代码思路：

    用$sum[i]$存前$i$件物品的和，每次枚举物品的时候，要注意$m-sum[i-1]-w[i]+1$小于$0$的情况，这时用$max(m-sum[i-1]-w[i]+1,0)$
    注意，每次枚举的过程中，我们要先将第$i+1...n$的物品装满剩余容积为$m-sum[i-1]-w[i]+1$  ~  $m-sum[i-1]$的结果加入到 $ans$ 中，然后再将当前物品加入到背包中

核心：灵活运用背包顺序与逆序的巧妙思路，最重要的是明白背包dp的本质，本题就运用这个思路逆序更新背包，实在巧妙

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n, m, ans;
int dp[1005], w[35], sum[35];int main() {int cas, n, m, t=0;scanf("%d", &cas);while(cas--) {sum[0]=ans=0;memset(dp, 0, sizeof(dp));scanf("%d%d", &n, &m);for(int i=1; i<=n; i++)scanf("%d", &w[i]);sort(w+1, w+n+1);for(int i=1; i<=n; i++)sum[i]=sum[i-1]+w[i];dp[0]=1;for(int i=n; i>=1; i--) {int k = max(m-sum[i-1]-w[i]+1, 0);for(int j=m-sum[i-1]; j>=k; j--)ans += dp[j];for(int j=m; j>=w[i]; j--)	//将第i个物品放入背包，即重新编排了一次背包dp[j] += dp[j-w[i]];}if(m<w[1]) ans=0;printf("%d %d\n", ++t, ans);}
}

这篇关于POJ-3093___Margaritas on the River Walk —— 01背包的变异的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---