diff options
| author | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
|---|---|---|
| committer | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
| commit | 4022e5c95210631e4aceb08eaf9d9071aa5aefc4 (patch) | |
| tree | a5922559836e45fb3459a3d070367912e1035b1a /tests/sysy_lvX/091_backpack.sy | |
| download | rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.gz rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.xz | |
Diffstat (limited to 'tests/sysy_lvX/091_backpack.sy')
| -rw-r--r-- | tests/sysy_lvX/091_backpack.sy | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/tests/sysy_lvX/091_backpack.sy b/tests/sysy_lvX/091_backpack.sy new file mode 100644 index 0000000..4813357 --- /dev/null +++ b/tests/sysy_lvX/091_backpack.sy @@ -0,0 +1,63 @@ +int V[200][200]={};
+int KnapSack(int n, int w[], int v[], int x[], int C)
+{
+ int i, j;
+ i=1;
+ while(i<=n)
+ {
+ j=0;
+ while(j<C+1)
+ {
+ if (j<w[i])
+ V[i][j] = V[i - 1][j];
+ else
+ {
+ int tmp1=V[i - 1][j];
+ int tmp2=V[i - 1][j - w[i]] + v[i];
+ if(tmp1>tmp2)
+ {
+ V[i][j] = tmp1;
+ }
+ else
+ {
+ V[i][j] = tmp2;
+ }
+
+ }
+ j=j+1;
+ }
+ i=i+1;
+ }
+
+ j = C;
+ i=n;
+ while(i>=1)
+ {
+ if (V[i][j]>V[i - 1][j])
+ {
+ x[i] = 1;
+ j = j - w[i];
+ }
+ else
+ {
+
+ x[i] = 0;
+ }
+ i=i-1;
+ }
+ return V[n][C];
+}
+
+int main()
+{
+ int s;
+ int w[6] = {0,2,2,6,5,4};
+ int v[6] = {0,6,3,5,4,6};
+ int x[6];
+ int n = 5;
+ int C=10;
+ s = KnapSack(n, w, v, x, C);
+ putint(s);
+ return 0;
+
+}
|