0-1背包问题

给定n种物品（每种仅一个）和一个容量为c的背包，要求选择物品装入背包，使得装入背包中物品的总价值最大。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据输入3行，第1行为两个整数n（1≤n≤400）和c (1≤c≤1500)，分别表示物品数量与背包容量，第二行为n个物品的重量wi​（1≤i≤n），第三行为这n个物品的价值vi​（1≤i≤n）。物品重量、价值都为整数。

输出格式:

对于每组测试，在一行上输出一个整数，表示装入背包的最大总价值（结果保证在231−1范围内）。

输入样例:

4 9
2 3 4 5
3 4 5 7
25 100
42 6 48 13 38 124 8 17 41 25 41 26 47 41 171 25 7 30 35 7 17 32 45 27 38
49 19 53 40 22 4 36 20 49 25 61 48 67 34 57 52 46 45 33 41 20 38 34 58 63

输出样例:

12
292

出处:

HLOJ 1006

#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
using namespace std;
typedef long long  ll;
#define N 401  
#define M 1501
int n,c;
int i,j;
int dp[N][M];//dp方程含义表示当重量为c时从n个物品里任意取出物品的最大价值
int weight[N];
int worth[N];
int solve()
{
    for(i=0;i<=c;i++) dp[0][i]=0; //初始化0个物品的时候价值都是0
    for(i=1;i<=n;i++)//遍历物品
    {
        for(j=0;j<=c;j++)//遍历重量
        {
            if(j<weight[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+worth[i]);
            //dp[i - 1][j - weight[i]] 为背包容量为j -weight[i]的时候不放物品i的最大价值，
            //那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
        }
    }
    return  dp[n][c];
}
int main()
{
    while(scanf("%d %d",&n,&c)!=EOF)
    {
        for(i=1;i<=n;i++) scanf("%d",&weight[i]);
        for(i=1;i<=n;i++) scanf("%d",&worth[i]);
        printf("%d\n",solve());
    }
}