01背包和完全背包（dp法）

任务描述

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

相关知识

动态规划

输入格式

第一行输入一个n，c，代表有n个物品背包容量为c
接下来n行，每行输入wi，和vi
其中0

输出格式

输出一个数，代表最大价值。

输入

4 8
2 3
3 4
4 5
5 6

输出

10

//01背包问题 

#include
#include
//using namespace std;

const int N=1e6+10;
int v[N];
int w[N];
int dp[N][N];

int main()
{
    int n,c;
    scanf("%d %d",&n,&c);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d %d",&w[i],&v[i]);
    }

    for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=c;j++)
		{
			if(j 
 
完全背包
 
 
任务描述 
现在有很多物品（它们是可以分割的）,每个物品有多个，我们知道它们每个物品的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为c（10<=c<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
 
输入格式 
第一行有两个正整数n，c（1<=n<=10）;n表示有n个物品。接下来的n行每行有两个正整数w,v。
 
输出格式 
输出一个数，代表最大价值。
 
输入样例 
3 15
 5 10
 2 8
 3 9
 
输出样例 
60
 
#include
#include
using namespace std;

//完全背包
int f[20][20];
int v[20],w[20];

int main()
{

    int n,m;
    scanf("%d %d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&w[i],&v[i]);
    }

    for(int i=1;i<=n;i++)
    {
    	for(int j=0;j<=c;j++)
    	{
            
    		f[i][j]=f[i-1][j];
    		if(j>=w[i])
    		f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
    	}
    }

    printf("%d",f[n][c]);  

    return 0;
}