动易网站建设工作室网站排行榜查询

描述

给定n种物品和一个背包，物品i的重量是Wi​，其价值为Vi​，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？

在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。

输入描述

第一行输入物品的个数n。

第二行输入物品的重量序列w。(中间有空格）

第三行输入物品的价值序列v。（中间有空格）

第四行输入背包容量c。

输出描述

第一行输出装入背包的物品。（用0和1表示，中间无空格）

第二行输出最大价值。

用例输入 1

3
3 4 5
4 5 6
10

用例输出 1

011
11

提示:

n<100;
1<Wi​,Vi​<100;

本题是典型的背包问题，唯一的难点就是如何查询背包元素。

思路：

利用逆推发，反向查找，如果本像元素与上一列元素一样，则没装，否则装了，由此可推出以下代码：

    string ans="";int W=c;for (int i=n;n>0 && s>0;i--){if (s==dp[i-1][W]) ans='0'+ans;else{ans='1'+ans;s-=v[i-1];W-=w[i-1];}}

则利用动态规划，将代码完善：

#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000]={0};
int main()
{int n;cin>>n;int w[n+1]={0},v[n+1]={0};for (int i=0;i<n;i++) cin>>w[i];//注意这里是单行输入重量。for (int i=0;i<n;i++) cin>>v[i];//单行输入价值。int c;cin>>c;    for (int i=1;i<=n;i++){for (int j=1;j<=c;j++){if (w[i-1]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);//动态规划else (dp[i][j]=dp[i-1][j]);}}int s=dp[n][c];//开始逆推string ans="";int W=c;for (int i=n;n>0 && s>0;i--){if (s==dp[i-1][W]) ans='0'+ans;else{ans='1'+ans;s-=v[i-1];W-=w[i-1];}}int k=n-ans.size();while (k--) ans='0'+ans;//处理一下cout<<ans<<endl<<dp[n][c];//输出
}