0 1背包解题报告 poj3624

动态规划算法思想：设m[i][j]用来表示从前i项物品中区取出装入体积为j的背包的物品的最大价值。

其中i的范围为0到n，其中j的范围为0到c，程序要寻求的解为m[n][c]。可以分以下三种情况：

 ①m[0][j]对所有的j的值为0(物品种类为0)， m[i][0]对所有的i的值为0(体积为0)

 ②当前的体积j大于等于w[i]时， m[i][j]是下面两个量的最大值：m[i-1][j](不装)和 m[i-1][j-w[i-1]]+v[i](装)

 ③当前的体积j小于w[i]时，m[i][j]等于m[i-1][j]

 

(0 1背包 滚动数组)

 

http://poj.org/problem?id=3624

 

#include<iostream>
using namespace std;
const int N=13000;
//w[N]表示物品的重量，v[N]表示物品的价值 c表示总容量 
int w[N],v[N],m[N],c,n;
int main()
{
    int i,j;
    while(cin>>n>>c){
        for(i=0;i<n;i++)  cin>>w[i]>>v[i];
        memset(m,0,sizeof(m));
        for(i=0;i<n;i++)
            for(j=c;j>=0;j--){
                if(j>=w[i])
                   m[j]=max(m[j],m[j-w[i]]+v[i]);//滚动数组 
            } 
        cout<<m[c]<<endl;
    }
    return 0;
} 

m数组是从上到下，从右往左计算的。在计算m(i,j)之前，m[j]里保存的就是是m(i-1,j)的值， 而m[j-w]里保存的是m(i-1,j-w)而不是m(i,j-w) --别忘了j是逆序枚举的，此时m(i,j-w)还没有出来。这样，m[j]>?m[j-w]+v实际是把max{f(i-1),f(i-1,j-w)}保存在m[j]中，覆盖掉m[j]原来的m(i-1,j).

 

 

采药(0 1背包):http://tyvj.cn/Problem_Show.asp?id=1005

 

#include<iostream>
using namespace std;
const int N=1005;
//w[N]表示物品的重量，v[N]表示物品的价值 
int w[N],v[N],m[N][N],t,n;
int main()
{
    int i,j;
    cin>>t>>n;
    for(i=0;i<n;i++)  cin>>w[i]>>v[i];
    
    for(i=1;i<=n;i++)
        for(j=1;j<=t;j++){
            m[i][j]=m[i-1][j];
            if(j>=w[i-1])
               m[i][j]=max(m[i-1][j],m[i-1][j-w[i-1]]+v[i-1]);
        } 
    cout<<m[n][t]<<endl;
    //system("pause");   
    return 0;
} 

 

装箱问题： http://tyvj.cn/Problem_Show.asp?id=1016

 

#include<iostream>
#include<cstring>
using namespace std;
const int N=20005;
int c,n,w[35],v[35],m[N]={0};

int main()
{
    cin>>c>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=c;j>=w[i];j--){ 
           m[j]=max(m[j],m[j-w[i]]+w[i]);
           //cout<<m[j]<<endl;
        }
     
    cout<<c-m[c]<<endl;
    return 0;
}