完全背包问题

时间:2023-01-30 04:21:56

完全背包问题:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将

哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

 

分析:状态转移方程为:

 

完全背包问题

 

于完全背包问题,与01背包比较只是v的循环顺序改变而已。

 

 

首先想想为什么01背包中要按照v=V..0的逆序来循环。

这是因为要保证第i次循环中的状态 dp[i][v]是由状态dp[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只

选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果dp[i-1][v-c[i]]。

而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第

i种物品的子结果dp[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

int Work(int c[],int w[],int n,int m)
{
dp[0]=0;
for(int v=1; v<N; v++)
dp[v]=INF;
for(int i=1; i<=n; i++)
for(int v=c[i]; v<=m; v++)
dp[v]=min(dp[v],dp[v-c[i]] + w[i]);
return dp[m];
}


 

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1114