OpenJudge_ 简单英文题_04:0/1 Knapsack

题目

描述
Given the weights and values of N items, put a subset of items into a knapsack of capacity C to get the maximum total value in the knapsack. The total weight of items in the knapsack does not exceed C.

输入
First line: two positive integers N (N <= 100) and C (C <= 1000).
Second line: N positive integers w[i] (w[i] <= 1000), indicating the weight of the i-th item.
Third line: N positive integers v[i] (v[i] <= 1000), indicating the value of the i-th item.
输出
One line contains several integers, indicating the indexes of the selected items.
样例输入
5 10
2 4 6 2 5
1 3 4 2 8
样例输出
2
5

翻译

题目：
0/1背包
描述：
给定N个物品的权重和值，将一个子集的物品放入容量为C的背包中，以获得背包中的最大总值。背包中物品的总重量不超过C。
输入：
第一行：两个正整数N（N<=100）和C（C<=1000）。
第二行：N个正整数w[i]（w[i]<=1000），表示第i个项目的权重。
第三行：N个正整数v[i]（v[i]<=1000），表示第i项的值。
输出：
一行包含几个整数，表示所选项目的索引。

代码

#include <bits/stdc++.h>
using namespace std;
int n,//物品数量
c,//背包容量
w[1001],//每物品重量
v[1001],//每物品价值
f[101][1001];//多少重量时对应的最大价值
/*
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
f[几个物品][重量]=最大(f[不要该物品][同样重量],f[不要该物品][重量-该物品重量]+该物品价值);
没有该重量时的最大价值+该物品价值。
*/
struct node{
int i,j;
}p[101][1001]; //该物品的上个物品
void view(){//观察数据
cout<<“数据：\n”;
cout<<“重量\t\t”;for(int j=0;j<=c;j++)cout<<j<<“\t”;cout<<endl;
for(int i=1;i<=n;i++){
cout<<i<<“:\t”<<w[i]<<“,”<<v[i]<<“\t”;for(int j=0;j<=c;j++)cout<<f[i][j]<<“\t”;cout<<endl;
cout<<“\t\t”;for(int j=0;j<=c;j++)cout<<p[i][j].i<<“,”<<p[i][j].j<<“\t”;cout<<endl;
}
cout<<endl;
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
cin>>n>>c;
//cout<<“物品数量”<<n<<“\t背包容量”<<c<<endl;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)//行，各物品
for(int j=0;j<=c;j++){//列，每重量
f[i][j]=f[i-1][j];//该重量时能取得的最大价值可以初步认定为不用该物品就取得的最大价值
p[i][j]=node{i-1,j};
if(j>=w[i])//如果重量超过该物品的重量，可以考虑用该物品
if(f[i][j]<f[i-1][j-w[i]]+v[i]){//不用该物品(i-1)不算该物品重量(j-w[i])时取得的最大价值上+该物品的价值
f[i][j]=f[i-1][j-w[i]]+v[i];
p[i][j]=node{i-1,j-w[i]};
}
}
//view();
stack s;
int pi=n,pj=c;
while(f[pi][pj]!=0){//只要有价值就算
node px=p[pi][pj];//找到前一状态
if(pj!=px.j)s.push(pi);//如果两状态的重量一样就不算。
pi=px.i,pj=px.j;
}
while(!s.empty()){//逆序输出采用的各物品
cout<<s.top()<<endl;s.pop();
}
return 0;
}

小结

动态规划就怕画表格，画完表格就清楚了。
初始状态是怎样，随着阶段的变化状态怎样变化。
然后就能找到动态转移方程。