题目描述

给定 n 种物品和一个容量为 c 的背包，物品 i 的重量是 wi，其价值为 vi。 问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

输入

第一行两个数 n, c 接下来一行n个数 v1,v2,.....,vn 再接下来一行n个数 w1,w2,....,wn (1 <= n <= 100, 1 <= c <= 1000, 1 <= vi <= 1000, 1 <= wi <= 1000)

输出

输出一个数，表示答案

样例输入

6 12
8 10 6 3 7 2
4 6 2 2 5 1

样例输出24

题目的意思大概了解了，要使背包的价值最大，上代码：

#include<bits/stdc++.h>
using namespace std;
int n,c;
int w[1000],v[1000],dp[1000][1000];//w:体积，v:价值，dp:动态规划数组
int main()
{
　　cin>>n>>c;
　　for(int i=1;i<=n;i++)
　　{
　　　　cin>>v[i];//输入
　　}
　　for(int i=1;i<=n;i++)
　　{
　　　　cin>>w[i];//输入
　　}
　　memset(dp,0,sizeof(dp));//初始化
　　for(int i = 1;i<=n;i++)
　　{
　　　　for(int j=1;j<=c;j++)
　　　　{
　　　　　　if(j<w[i])//如果放不下
　　　　　　{
　　　　　　　　dp[i][j]=dp[i-1][j];//直接用上面的·
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//如果放得下就比较放和不放那个更大
　　　　　　}
　　　　}
　　}
　　cout<<dp[n][c];输出要找的价值的最大值
}