poj 3624 (0-1背包)

问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

空间优化：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}; //等价于状态转移方程，用一维数组代替二维数组

初始化细节：
若要求恰好装满背包，初始化时除了f[0]为0其它f[1..V]均设为-∞
若没有要求必须把背包装满，初始化时将f[0..V]全部设为0

[cpp]
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
//c记录物品费用，w记录物品价值；
int c[3500],w[3500],f[13000];
int main()
{
    int i,j,n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=0;i<n;i++)scanf("%d%d",&c[i],&w[i]);
        memset(f,0,sizeof(f));
        for(i=0;i<n;i++){ //主循环,确定物品数为i(即前i种)
            for(j=m;j>=c[i];j--){ //在给定物品时，改变背包容量j
                f[j]=max(f[j],f[j-c[i]]+w[i]);
            }
        }
        printf("%d\n",f[m]);
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
//c记录物品费用，w记录物品价值；
int c[3500],w[3500],f[13000];
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=EOF){
  for(i=0;i<n;i++)scanf("%d%d",&c[i],&w[i]);
  memset(f,0,sizeof(f));
  for(i=0;i<n;i++){ //主循环,确定物品数为i(即前i种)
   for(j=m;j>=c[i];j--){ //在给定物品时，改变背包容量j
    f[j]=max(f[j],f[j-c[i]]+w[i]);
   }
  }
  printf("%d\n",f[m]);
}
return 0;
}

补充：软件开发 , C++ ,