首页 > 代码库 > 01背包【模板】

01背包【模板】

2024-07-13 09:54:49   226人阅读

01背包是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i,v] 表示前i 件物品恰放入一个容量为v 的背包可以获得的最大价值。则其状态转移方程便是：
F[i,v]=max(F[i,v],F[i-1,v-w[i]]+v[i])
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i 件物品放入容量为v 的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只和前 i - 1 件物品相关的问题。如果不放第i 件物品，那么问题就转化为“前i - 1 件物品放入容量为v 的背包中”，价值为F[i - 1; v]；如果放第i 件物品，那么问题就转化为“前i - 1 件物品放入剩下的容量为v - Ci 的背包中”，此时能获得的最大价值就是F[i - 1; v - Ci] 再加上通过放入第i 件物品获得的价值Wi。伪代码如下：
F[0,0..V ]<--0
for i<--1 to N
    for v<--Ci to V

         F[i; v]<--max{F[i - 1, v], F[i - 1, v - Ci] +Wi}

代码如下：

# include <stdio.h>  
# include <stdlib.h>  
# include <string.h>  
# define max(x,y) x>y?x:y;  
int v[1001];//价值  
int w[1001];//重量  
int dp[1001][1001];  
int main()  
{  
    int n,m,i,j;  
    while(scanf("%d%d",&m,&n)!=EOF)  
    {  
        memset(dp,0,sizeof(dp));//初始化  
        for(i=1; i<=n; i++)  
            scanf("%d%d",&w[i],&v[i]);  
        for(i=1; i<=n; i++) // 物品数  
            for(j=m; j>=w[i]; j--) //放入背包  
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);// 与前面对比  
        printf("%d\n",dp[n][m]);  
    } 
	return 0;
}


01背包【模板】


联系
我们