背包问题……典型0-1背包！题曰：今有n个物品，第i个体积为V[i]，价值为W[i]，背包的容积为C。求在体积不超容积的前提下，背包中可装物品价值的最大值。
输入 第一行：两个整数 n 和 C ； 第二行~第n+1行：每行两个整数Vi与Wi，有一个空格分隔。 输出 一个数，表示背包中能得到物品价值的最大值。 输入示例 2 10 1 1 2 2 输出示例 3 其他说明 数据范围：1 <= n <= 100； 1<= Vi,Wi <= 100； 1 <= C <= 10000。#include <iostream> using namespace std; int f[101][101],a[10010],b[10010],n,v; int max(int x,int y) { if(x>y) return x; else return y; } int main() { cin>>n>>v; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) { for(int j=a[i];j<=v;j++) { if(b[i]<v) f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]); else f[i][j]=f[i-1][j]; } } cout<<f[n][v]; } View Code
转载于:https://www.cnblogs.com/jason2003/p/6574371.html
