又见01背包

Dear 丶 2022-08-05 05:05 143阅读 0赞

**时间限制**：1000 ms | **内存限制**：65535 KB |  **难度**：3  
**描述** 有n个重量和价值分别为wi 和 vi 的 物品，从这些物品中选择总重量不超过 W 的物品，求所有挑选方案中物品价值总和的最大值。

1 <= n <=100  
　　1 <= wi <= 10^7  
　　1 <= vi <= 100  
　　1 <= W <= 10^9

**输入**  
多组测试数据。  
每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。  
**输出**  
 满足题意的最大价值，每组测试数据占一行。  
**样例输入**  
4 5  
2 3  
1 2  
3 4  
2 2  
样例输出  
7

#include <stdio.h>
    #include <string.h>
    
    #define MAX_NUM 101
    
    #define min(a,b) ((a)>(b))?(b):(a)
    
    int wi[MAX_NUM];
    int vi[MAX_NUM];
    int dp[MAX_NUM*MAX_NUM];
    
    int main()
    {
    	/**
    	 *　 1 <= n <= 100 	物品个数
    	 *  1 <= wi <= 10^7	重量
    	 *  1 <= vi <= 100 	价值
    	 *  1 <= W <= 10^9 	总重量
    	 */
    	int n = 0;
    	int W = 0;
    
    	/**
    	 * 多组测试数据。
    	 * 每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的 wi 和 vi。
    	 *
    	 */
    
    	while(scanf("%d %d",&n,&W) != EOF)
    	{
    		int i = 0;
    		int j = 0;
    		int Answer = 0;
    
    		Initial & Input/
    		memset(dp,0,sizeof(dp));
    		memset(wi,0,sizeof(wi));
    		memset(vi,0,sizeof(vi));
    
    		int sumVi = 0;
    
    		for (i = 1; i <= n; i++)
    		{
    			scanf("%d %d",&(wi[i]),&(vi[i]));
    			sumVi += vi[i];
    		}
    
    		for (j = 0; j <= sumVi; j++)
    		{
    			dp[j] = 1000000001;
    		}
    
    		dp[0] = 0;
    
    		Initial & Input/
    
    		/**
    		 *  互换 质量和重量，求价值在  i 时候重量的最小值，这个是恰好等于 i 的时候
    		 */
    
    		for (i = 1; i <= n; i++)
    		{
    			for (j = sumVi; j > 0 ; j--)
    			{
    				if (j-vi[i] >= 0)
    				{
    					dp[j] = min(dp[j],dp[j-vi[i]]+wi[i]);
    
    					if (dp[j] <= W)
    					{
    						Answer = Answer > j ? Answer : j;
    					}
    				}
    			}
    		}
    
    		printf("%d\n",Answer);
    	}
    
    	return 0;
    }