背包问题简单整理-白红宇

背包问题简单整理

阅读量：7174 次

发布时间：2019-06-29

本文共 1159 字，大约阅读时间需要 3 分钟。

hdu2546,01背包，需要有点变形，计算时需要把价格最大的菜先放一边，最后计算。

#include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;int V;int dp[1200];void ZeroOnePack(int ci,int wi){ for(int v=V-5;v>=ci;--v) dp[v] = max(dp[v],dp[v-ci]+wi);}int main(){ //freopen("test.txt","r",stdin); int n; while(true) { scanf("%d",&n); if(n==0) break; memset(dp,0,sizeof(dp)); int vi[1200]; int iMaxIndex = 0; int iMaxVal = -10; for(int i=0;i

View Code

hdu 2191 多重背包，多重背包主要可以分解成01背包和完全背包。

#include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;int V,n;int dp[200];void ZeroOnePack(int vi,int wi){ for(int v=V;v>=vi;--v) dp[v] = max(dp[v],dp[v-vi]+wi);}void CompletePack(int vi,int wi){ for(int v=vi;v<=V;++v) dp[v] = max(dp[v],dp[v-vi]+wi);}void MultiPack(int vi,int wi,int ki){ if(vi*ki >= V) { CompletePack(vi,wi); } else { for(int k=1;k