完全背包问题：湫湫系列故事――减肥记I（HDU 4508）

湫湫系列故事――减肥记I HDU 4508

一道裸的完全背包

 #include<iostream>

 #include<algorithm>

 #include<stdio.h>

 #include<string.h>

 using namespace std;

 int c[],a[],b[];

 int main()

 {

     int n,i,j,m;

     while(scanf("%d",&n)!=EOF)

     {

         for(i=;i<n;i++)

             scanf("%d%d",&a[i],&b[i]);

         scanf("%d",&m);

         memset(c,,sizeof(c));

         for(i=;i<n;i++)

             for(j=b[i];j<=m;j++)

                 if(c[j]<c[j-b[i]]+a[i])

                 c[j]=c[j-b[i]]+a[i];

         printf("%d\n",c[m]);

     }

     return ;

 }

下面是没有二进制优化的算法：

思路：

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……直至取⌊V/Ci⌋件等许多种。
如果仍然按照解01背包时的思路，令F[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
F[i,v]=max{F[i−1,v−kCi]+kWi|0≤kCi≤v}
这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不
是常数了，求解状态F[i,v]的时间是O(vCi)，总的复杂度可以认为是O(NVΣVCi)，是比较大的。

 #include<iostream>

 #include<algorithm>

 #include<stdio.h>

 #include<string.h>

 using namespace std;

 int c[],a[],b[];

 int main()

 {

     int n,i,j,k,m;

     while(scanf("%d",&n)!=EOF)

     {

         for(i=;i<n;i++)

             scanf("%d%d",&a[i],&b[i]);

         scanf("%d",&m);

         memset(c,,sizeof(c));

         for(i=;i<n;i++)

             for(k=0;k<=m/b[i];k++)//数量

             for(j=m;j>=k*b[i];j--)

             c[j]=max(c[j],c[j-k*b[i]]+k*a[i]);

         printf("%d\n",c[m]);

     }

     return ;

 }

巴特西

完全背包问题：湫湫系列故事――减肥记I（HDU 4508）

最新文章

热门文章