本文共 1294 字,大约阅读时间需要 4 分钟。
You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.
You want to find a subset of items to put such that:
Find the maximum total value of items in the knapsack.
N Wv1 w1v2 w2:vN wN
The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.
Print the maximum total values of the items in a line.
4 54 25 22 18 3
13
2 205 94 10
9
递推关系:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-b[i].w]+b[i].v);
注意要做好初始化。。。
代码如下:
#include#include #include #include using namespace std;const int maxn=105;const int maxw=10005;int n,w;struct bag{ int v; int w;};bag b[maxn];int dp[maxn][maxw];int main(){ scanf("%d%d",&n,&w); for (int i=1;i<=n;i++) scanf("%d%d",&b[i].v,&b[i].w); for (int i=0;i<=w;i++) dp[0][i]=0; for (int i=1;i<=n;i++) dp[i][0]=0; for (int i=1;i<=n;i++) { for (int j=1;j<=w;j++) { dp[i][j]=dp[i-1][j]; if(j
转载地址:http://cxaen.baihongyu.com/