背包有关问题求解

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

c代码是这样，有2处不理解，请帮忙解答谢谢

#include "stdio.h"  
    #define max(a,b) ((a)>(b)?(a):(b))  
      
      
      
    main(){  
          
        int v = 10 ;    
        int n = 5 ;      
           
        int value[] = {0, 8 , 10 , 4 , 5 , 5};       
        int weight[] = {0, 6 , 4 , 2 , 4 , 3};     
        int i,j;      
        int dp[n+1][v+1];  
        for(i = 0; i < n+1; i++)  
            for(j = 0; j < v+1; j++)  
                dp[i][j] = 0;  
      
      
        for(i = 1; i <= n; i++){  
            for(j = 1; j <= v; j++){  
                if(j >= weight[i])  
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);  
                else  
                    dp[i][j] = dp[i-1][j];  
            }  
        }  
      
        printf("%d",dp[n][v]);  
    }  

 if(j >= weight[i])  
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);  
                else  
                    dp[i][j] = dp[i-1][j]; 



这段代码 中：


1，if（j >= weight[i]）里面的判断怎么说？
 
2，第二处的 dp[i - 1][j - weight[i]] + value[i]
的 dp[i - 1][j - weight[i]]
不理解请帮忙解答

[解决办法]
>if（j >= weight[i]）里面的判断怎么说？
总重8不可能由添加一个重量为10的物体所得到。所以直接copy过去了。
>dp[i - 1][j - weight[i]]
使用前i-1个物体（的其中几个），达到j-weight[i]这个重量的最优解。
[解决办法]
你还没理解dp这个数组存放的值意义是什么。

查看更多 下一篇