完全背包问题:有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