ACM_01背包2

背包4

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

有n个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过W的物品，求所有方案中价值总和的最大值。

Input:

输入包含多组测试用例，每一例的开头为两位整数 n、W;接下来有 n 行，每一行有两位整数 Wi、Vi

其中：

1<=n<=100

1<=W<=1000,000,000（10^9）

1<=Wi<=10,000,000（10^7）

1<=Vi<=100。

Output:

输出为一行，即所有方案中价值总和的最大值。

Sample Input:

Sample Output:

7

10
解题思路：相比01背包，这题只是修改了限制条件的大小，此前求解这一问题的时间复杂度是O（nW），但是对于这一问题，W最大为10^9，显然使用之前的方法会超时。但是可以发现，相比较重量而言，价值的范围比较小，因此换种角度可以解决此题。之前的方法中，dp[j]是求解当前重量j不超过总重量W下的最大价值，而这次的dp[i][j]表示从前i个物品中挑选价值总和为j（从0开始枚举）时总重量的最小值（不存在时就是一个充分大的INF）。因此最终的答案就对应于令dp[n][i]<=W的最大的i（i从总价值V～0枚举）。
二维数组状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])。
一维数组状态转移方程：dp[j]=min(dp[j],dp[j-v[i]]+w[i])(j:V～v[i])。
AC代码一：二维数组实现。

 #include<bits/stdc++.h>

 using namespace std;

 int n,W,V,w[],v[],dp[][];

 int main(){

     while(cin>>n>>W){

         memset(dp,0x3f,sizeof(dp));

         V=,dp[][]=;//从前0个物品挑选出价值总和为0的最小重量为0

         for(int i=;i<=n;++i)

             cin>>w[i]>>v[i],V+=v[i];

         for(int i=;i<=n;++i){

             for(int j=;j<=V;++j){

                 if(j<v[i])dp[i][j]=dp[i-][j];

                 else dp[i][j]=min(dp[i-][j],dp[i-][j-v[i]]+w[i]);

             }

         }

         for(int i=V;i>=;--i)//找最大价值的物品且得放进重量为W的背包里面

             if(dp[n][i]<=W){cout<<i<<endl;break;}

     }

     return ;

 }

AC代码二：一维数组实现。

 #include<bits/stdc++.h>

 using namespace std;

 int n,W,V,w[],v[],dp[];

 int main(){

     while(cin>>n>>W){

         memset(dp,0x3f,sizeof(dp));//初始化为无穷

         V=,dp[]=;//价值总和为0的最小重量为0

         for(int i=;i<=n;++i)

             cin>>w[i]>>v[i],V+=v[i];//累加价值

         for(int i=;i<=n;++i)

             for(int j=V;j>=v[i];--j)

                 dp[j]=min(dp[j],dp[j-v[i]]+w[i]);

         for(int i=V;i>=;--i)//找最大价值的物品且得放进重量为W的背包里面

             if(dp[i]<=W){cout<<i<<endl;break;}

     }

     return ;

 }

巴特西

ACM_01背包2

背包4

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章