背包 習題HDU

01背包

HDU 2602

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int f[N];
int val[N],vol[N];
int main()
{
    int T;
	cin>>T;
	while(T--)
	{
		int n,V;
    	cin>>n>>V;
    	memset(f,0,sizeof(f));		//注意要初始化，否則WA 
    	for(int i=0;i<n;i++)
    	{
    	    cin>>val[i];
    	}
    	for(int i=0;i<n;i++)
    	{
    	    cin>>vol[i];
    	}
    	for(int i=0;i<n;i++)
    	{
        	for(int j=V;j>=vol[i];j--)
        	{
        	    f[j]=max(f[j],f[j-vol[i]]+val[i]);
        	}
    	}
   		cout<<f[V]<<endl;
	} 
    return 0;
}
           

HDU 2546

//本題中将菜的價格看做 背包中的價值 和 體積，即價值與體積相等的情況 
//把卡的餘額看做 背包的容量 
//思路是 把最貴的菜放到最後，在 n-1 之前将餘額花到最接近 5元 ，即求接近5元 的最大消費 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N];
int val[N];

int main()
{
	int n;
	while(cin>>n,n)
	{
		memset(f,0,sizeof(f));
		for(int i=0;i<n;i++)
		{
			cin>>val[i];
		}
		sort(val,val+n);//排序将最貴的菜放到最後 
		int m;
		cin>>m;
		int V=m-5;		//最大容量就是可以花到的最大金額，使得餘額最接近 5 元 
		if(m<5)			//如果餘額已經小于 5 元，則輸出 
		{
			cout<<m<<endl;
			continue;
		}
		for(int i=0;i<n-1;i++)		//前 n-1 個菜 
		{
			for(int j=V;j>=val[i];j--)
			{
				f[j]=max(f[j],f[j-val[i]]+val[i]);
			}
		}
		cout<<m-f[V]-val[n-1]<<endl;		//餘額減去最大消費，減去最貴的菜價格 
	}
	return 0;
} 
           

完全背包

HDU 1114

小豬存錢罐裝滿的重量減去空時的重量，為 小豬存錢罐的容量v=F-E , 應用完全背包的知識求得最少的硬币。

#include<iostream>
using namespace std;
const int N=10010;
const int INF = 1e9;
int f[N];
int val[N],weight[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		
		int E,F;
		int v,n;
		cin>>E>>F;
		v=F-E;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>val[i]>>weight[i];
		}
		//一定要注意初始化 
		fill(f,f+10010,INF);
        f[0]=0;
		int MAx=INF;
		for(int i=0;i<n;i++)
		{
			for(int j=weight[i];j<=v;j++)
			{
				f[j]=min(f[j],f[j-weight[i]]+val[i]);
			}
			
		}
		//注意判斷條件
		if(f[v]>=INF)
		{
			cout<<"This is impossible."<<endl;
		}
		else
		{
			cout<<"The minimum amount of money in the piggy-bank is "<<f[v]<<"."<<endl;
		}
	}
	return 0;
	
} 
           

HDU 2159

本題說每種怪都有無數個，是以可以看做完全背包問題。其中要考慮忍耐度和殺怪數量兩個因素，所求的的經驗值要 > n ,是以要開一個二維數組 j 表示忍耐值 k 表示殺怪數量（注意循環中的順序）

#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
const int INF=1e9;
int f[N][N];
int val[N],w[N];
int main()
{
	int n,m,k,s;
	while(cin>>n>>m>>k>>s)
	{
		for(int i=0;i<k;i++)
		{
			cin>>val[i]>>w[i];
		}
		int ren=INF;
		memset(f,0,sizeof(f));
		for(int i=0;i<k;i++)
		{
			for( int j=w[i];j<=m;j++)
			{
				for(int k=s-1;k>=0;k--)
				{
					f[j][k]=max(f[j][k],f[j-w[i]][k+1]+val[i]);
					if(f[j][k]>=n&&j<ren) ren=j;
				}
			}
		}
		//注意判斷條件
		if(ren< INF)
		{
			cout<<m-ren<<endl;
		}
		else
		{
			cout<<"-1"<<endl;
		}
	}
}
           

多重背包

HDU 2191

#include <cstring>
#include <algorithm>
// 多重背包求得最大價值 
#include <iostream>
#include<cmath>
using namespace std;
 
const int N = 10010;
int  v[110], w[110], num[110];
//多重背包：v表示價值，w表示空間，num表示個數
int val[1010], weight[1010];
//01背包：val表示新的價值，weight表示新的空間 
int dp[N];
 
int main() { 
    int T;
    cin>>T;
    while(T--) 
	{   int n,m;
		cin>>m>>n; 
        int count = 0;
        for(int i = 0; i < n; i++) 
		{  
            cin>>v[i]>>w[i]>>num[i];
            for(int j = 1; j <= num[i]; j << 1) {
                val[count] = j * v[i];
                weight[count++] = j * w[i];
                num[i] -= j;
            }
            if(num[i] > 0) {
                val[count] = num[i] * v[i];
                weight[count++] = num[i] * w[i];
            }
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < count; i++) {
            for(int j = m; j >= val[i]; j--) {
                dp[j] = max(dp[j], dp[j - val[i]] + weight[i]);
            }
        }
       cout<<dp[m]<<endl;
    }  
    return 0;  
}