2696: 动态规划-01背包问题
金币值：3
定数：7
时间限制：1.000 s
内存限制：128 M
正确：3
提交：6
正确率：50.00% 命题人：
题目描述
给定n（1<=n<=10）种物品和一背包，物品i (1≤i≤n) 的重量是wi (wi > 0)，其价值为vi (vi > 0)，背包的容量为c (0<c<=20)，问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
测试代码 复制
#include "stdio.h"
int m[11][21],w[11],v[11]; //第0行不存放有效数据
int knapbag(int n, int c) {
for(int j=0; j<=c; j++){//填写第n行数据
}
for(int i=n-1; i>=1; i--) { //分别填写第n-1,n-2,...1行数据
}
return m[1][c];//返回最大值
}
int main(void) {
int n,c,result; //1<=n<=10; 0 < c <= 20
scanf("%d %d",&n,&c);
for (int i=1; i<=n; i++) scanf("%d",&w[i]);
for (int j=1; j<=n; j++) scanf("%d",&v[j]);
result=knapbag(n,c);
printf("%d\n",result);
return 0;
}输入格式
第一行输入两个整数，分别表示n个物品和背包容量c
第二行输入n个整数，分别表示每个物品的重量
第三输入n个整数，分别表示每个物品的价值
第二行输入n个整数，分别表示每个物品的重量
第三输入n个整数，分别表示每个物品的价值
输出格式
第一行输出最大价值
输入样例 复制
3 10
4 3 5
50 40 60输出样例 复制
110提示
给定3种物品和一背包。物品的重量分别是{3，4，5}，价值分别为{4，5，6}，背包的容量为c (c = 10)。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求手工填写表格。