题意：完全背包
思路：完全背包
可以直接转化为 多重背包，num[i]=_v/c[i];//转为多重背包
然后运用 多重背包 3种解法如下
码1：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dp[100010]; int main() { int i,j,k,tem; int t,n,_v;//测试用例个数，物品种类，背包大小 int c[110],v[110];//花费，价值 int num[110];//每种物品个数 int tc,tv;//拆分时物品花费，价值 while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(i=1; i<=n; ++i)scanf("%d%d",&v[i],&c[i]); scanf("%d",&_v); for(i=1; i<=n; ++i)num[i]=_v/c[i];//转为多重背包 ////// for(i=1; i<=n; ++i) for(k=_v; k>=c[i]; --k) for(j=1; j<=num[i]&&j*c[i]<=k; ++j)//此处比01背包多了一层循环 { tc=j*c[i]; tv=j*v[i]; tem=dp[k-tc]+tv; if(tem>dp[k])dp[k]=tem; } // printf("%d ",dp[_v]); } return 0; }
码2：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dp[100010]; int main() { int i,j,k,tem; int t,n,_v;//测试用例个数，物品种类，背包大小 int c[110],v[110];//花费，价值 int num[110];//每种物品个数 int tc,tv;//拆分时物品花费，价值 while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(i=1; i<=n; ++i)scanf("%d%d",&v[i],&c[i]); scanf("%d",&_v); for(i=1; i<=n; ++i)num[i]=_v/c[i];//转为多重背包 ////// for(i=1; i<=n; ++i) for(j=1; j<=num[i]&&j*c[i]<=_v; ++j)//此处比01背包多了一层循环 for(k=_v; k>=j*c[i]; --k) { tem=dp[k-c[i]]+v[i]; if(tem>dp[k])dp[k]=tem; } // printf("%d ",dp[_v]); } return 0; }
码3：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dp[100010]; int main() { int i,j,k,tem; int t,n,_v;//测试用例个数，物品种类，背包大小 int c[110],v[110];//花费，价值 int num[110];//每种物品个数 int tc,tv;//拆分时物品花费，价值 while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(i=1; i<=n; ++i)scanf("%d%d",&v[i],&c[i]); scanf("%d",&_v); for(i=1; i<=n; ++i)num[i]=_v/c[i];//转为多重背包 ////// for(i=1; i<=n; ++i) { for(j=1; j<=num[i]; num[i]=num[i]-j,j=j*2)//此处比01背包多了一层循环 { tc=j*c[i];//拆分后物品花费 tv=j*v[i];// for(k=_v; k>=tc; --k) { tem=dp[k-tc]+tv; if(tem>dp[k])dp[k]=tem; } } if(num[i]>0) //如果还有物品，num[i] 即相当于 1+2+4+...+q 中的 q { tc=num[i]*c[i]; tv=num[i]*v[i]; for(k=_v; k>=tc; --k) { tem=dp[k-tc]+tv; if(tem>dp[k])dp[k]=tem; } } } // printf("%d ",dp[_v]); } return 0; }
另外：附一种更高效的方法 O(n*_v)
与01背包代码中内层循环相反
1...n
0..._v
码4：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dp[100010]; int main() { int i,j; int t,n,_v;//测试用例个数，物品种类，背包大小 int c[110],v[110];//花费，价值 while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(i=1; i<=n; ++i)scanf("%d%d",&v[i],&c[i]); scanf("%d",&_v); for(i=1; i<=n; ++i) for(j=c[i];j<=_v;++j) if(dp[j-c[i]]+v[i]>dp[j])dp[j]=dp[j-c[i]]+v[i]; printf("%d ",dp[_v]); } return 0; }