【背包的其他问法】恰好、至少装满，方案数

【背包的其他问法】恰好、至少装满，方案数

文章目录

• • 背包恰好装满
  • 背包至少装满，且价值最少
  • 恰好装满的方案数
  • 还有一种特殊的，物品的一个性质同时充当v和w

背包恰好装满

• DP背包问题的 恰好装满 问题 ~~
• 恰好装满背包，又分为价值最大和价值最小

• 根据 d p dp dp 函数的定义不同， d p [ 0 , 0 − V ] dp[0,0-V] dp[0,0−V] 初始化值也不同
• d p [ i , j ] dp[i,j] dp[i,j] 定义为前 i i i 个物品 上限( or 刚好装满的限度)

1. V V V 为上限时， d p [ 0 , 0 − V ] dp[0,0-V] dp[0,0−V] 为有效状态，且易得值为0.
2. 要求刚好装满的限度为 V V V 时，只有 d p [ 0 , 0 ] dp[0,0] dp[0,0] 为有效状态，易得值为0.
   其他都是无效状态，初始为无穷。

背包至少装满，且价值最少

• 可以转化为恰好装满，且价值最少。那么答案就落在 V − V + m a x ( v i ) V-V+max(v_i) V−V+max(vi​).

• 为啥答案范围上限是 V + m a x ( v i ) V+max(v_i) V+max(vi​) 呢？因为物品体积最大是 m a x ( v i ) max(v_i) max(vi​) ，就有可能超出 V V V 刚好 m a x ( v i ) max(v_i) max(vi​) 。

• P2918 [USACO08NOV]Buying Hay S

• 代码：

#include <iostream>
#include<cstdio>
using namespace std;const int N=55005;
int dp[N],w[N],v[N];int main()
{int n,V; cin>>n>>V;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<N;i++) dp[i]=1e9;for(int i=1;i<=n;i++)for(int j=v[i];j<=V+5000;j++)dp[j]=min(dp[j],dp[j-v[i]]+w[i]);int res=1e9;for(int i=V;i<=V+5000;i++) res=min(res,dp[i]);cout<<res;return 0;
}

恰好装满的方案数

• 由 d p dp dp 函数定义可知，初始化时，只有 d p [ 0 , 0 ] dp[0,0] dp[0,0] 为1，即前零个物品组合为0的方案有一种。 d p [ 0 , 1 − V ] dp[0,1-V] dp[0,1−V] 则为0.
• 转移时则按子状态空间进行转移， d p [ i , j ] = ∑ d p [ i − 1 , 子 状 态 ] dp[i,j]=sum{dp[i-1,子状态]} dp[i,j]=∑dp[i−1,子状态]

还有一种特殊的，物品的一个性质同时充当v和w

P1049 [NOIP2001 普及组] 装箱问题